题解：P7800 [COCI 2015/2016 #6] PAROVI

· · 题解

P7800 [COCI 2015/2016 #6] PAROVI

Tag：DP

把问题转换为：选取一些 [1,n] 的子区间，它们的端点编号互质，且这些区间覆盖 [1, n] 的方案数（区间 [l,k] 和 [k+1,r] 不算覆盖 [l,r]）。

我们先预处理所有合法区间，复杂度 O(n^2\log n)。

考虑怎么描述合法方案：从前缀 1 开始，不断往后面接区间，保证后面接的区间 "左端点 \le 当前前缀的右端点，右端点 > 当前前缀的右端点"；然后中间还有一些被包含的无用区间，它们选不选都不影响合法性，也需要算上方案。

针对这个构造方法，我们可以先把所有区间按照左端点升序排序。

那么我们现在考虑怎么不重不漏地计算：

  1. 直接模拟构造的过程，设 f(i,j) 表示考虑了前 i 个区间，覆盖了前缀 [1,j]，且 \forall k>j，都有前缀 [1,k] 没被覆盖，的方案数。

  2. 假设当前考虑区间 [l,r]，

    • 若 l\le j，则 f(i,j)\to f(i+1,\max\{j,r\})，代表要么往后接一段，要么添加一个无用区间。

    • 当 l\le j 时也可以不选这个区间，f(i,j)\to f(i+1,j)。

    • 若 l>j，添加这个区间不会使覆盖的前缀增加，则 f(i,j)\to f(i+1,j)。

复杂度上界 O(n^3)。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int N = 25, MOD = 1e9;

int gcd(int a, int b) {
    if (a < b) swap(a, b);
    if (!b) return a;
    return gcd(b, a % b);
}

int n, m, f[N * N][N];
vector<PII> rec;

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (gcd(i, j) == 1) {
                rec.push_back({i, j});
            }
        }
    }
    for (auto [x, y] : rec);
    m = rec.size();
    sort(rec.begin(), rec.end(), [&](auto i, auto j) { return i.first == j.first ? i.second < j.second : i.first < j.first; });
    f[0][1] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 1; j <= n; j++) {
            if (f[i][j]) {
                (f[i + 1][j] += f[i][j]) %= MOD;
                if (rec[i].first > j) continue;
                (f[i + 1][max(j, rec[i].second)] += f[i][j]) %= MOD;
            }
        }
    }
    cout << f[m][n] << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}