题解：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

当前前缀的右端点，右端点

>

当前前缀的右端点"；然后中间还有一些被包含的无用区间，它们选不选都不影响合法性，也需要算上方案。

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

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

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

。

CPP

#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;
}

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

文章操作

相关推荐

评论

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