我永远喜欢39号同学2018。

xh39 · 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;
}