自动搬运

查看原文

来自洛谷，原作者为

	xh39 **

搬运于2025-08-24 22:33:12，当前版本为作者最后更新于2021-10-07 13:44:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先理解题意，其实就是用若干条线段完全覆盖 $[1,n]$。(把选中的 $a,b$ 完全理解为线段。如果完全覆盖就无法选出合法的 $x$。)

最暴力的方法是直接枚举这些线段选不选。复杂度 $O(n\times 2^{m})$。

首先将所有区间按右端点排序。可以顺序枚举右端点，再枚举左端点看是否互质。

对于搜索的优化方法很容易想到dp。设 $f(i,j)$ 为选前 $i$ 条，完全覆盖 $[1,j]$ 有多少种方案。

当 $l_{i+1}<=j$ 时，若选，则 $[1,r_{i+1}]$ 被覆盖(因为排了序，所以 $r_{i+1}>=j$)。否则覆盖的区间仍然是 $[1,j]$。

当 $l_{i+1}>j$ 时，则无论选不选都有一段区间未被覆盖都是转移到 $f(i,j)$。

所以用代码写就是:

f[i+1][j]=(f[i+1][j]+f[i][j])%mod;
if(a[i+1].l<=j){
    f[i+1][a[i+1].r]=(f[i+1][a[i+1].r]+f[i][j])%mod;
}else{
    f[i+1][j]=(f[i+1][j]+f[i][j])%mod;
}

为什么当 $l_{i+1}>j$ 时的处理一定是对的呢?因为之后还是得把 $[j+1,l_i]$ 给覆盖，然后又因为我们首先排了一遍序，覆盖这段区间的线段右端点一定大于或等于 $r_i$。意味着 $[l_{i+1},r_{i+1}]$ 依然会被覆盖，所以选第 $(i+1)$ 条线段对覆盖是没有意义的。

完整代码:

#include<iostream>
using namespace std;
struct xyq{
	int l,r;
}a[1000005];
int gcd(int a,int b){
	if(!b){
		return a;
	}
	return gcd(b,a%b);
};
long long f[1005][1005];
#define mod 1000000000
int main(){
	int n,i,j,tot=0,ykb;
	cin>>n;
	for(i=1;i<=n;i++){
		for(j=1;j<i;j++){
			if(gcd(j,i)==1){
				a[tot].l=j;
				a[tot].r=i;
				tot++;
			}
		}
	}
	f[0][a[0].r]=f[0][1]=1; 
	for(i=0;i<tot-1;i++){
		for(j=1;j<=n;j++){
			f[i+1][j]=(f[i+1][j]+f[i][j])%mod;
			if(a[i+1].l<=j){
				f[i+1][a[i+1].r]=(f[i+1][a[i+1].r]+f[i][j])%mod;
			}else{
				f[i+1][j]=(f[i+1][j]+f[i][j])%mod;
			}
		}
	}
	cout<<f[tot-1][n];
	return 0;
}