题意

选择一些 $n$ 一下互质的二元组 $\{a,b\}$，求对于任意 $x\in \big[2,n\big]$ 都不满足 $a,b<x$ 和 $a,b\ge x$ 的个数。

简化题意

因为无解的情况只发生在所有的 $\{a,b\}$ 之间没有多余的位置用于放置 $x$，所以题意可以抽象成这样：

选择一些区间互质的区间 $[a,b]$ 覆盖 $[1,n]$ 的方案数。

思路

设计 $f_{i,j}$ 表示前 $i$ 个字符覆盖区间 $[1,j]$ 的方案数。

对于 $f_{i,j}$，有一下合法的操作：

• 不选择第 $i$ 个线段，即 $f_{i,j}=f_{i,j}+f_{i-1,j}$。
• 选择第 $i$ 条线段并且第 $i$ 条线段的左端点可以覆盖到 $j$，即 $f_{i,r_i}=f_{i,r_i}+f_{i-1,j}$。
• 选择第 $i$ 条线段并且第 $i$ 条线段的左端点不可以覆盖到 $j$，对答案覆盖的右端点没有贡献，即 $f_{i,j}=f_{i,j}+f_{i-1,j}$。

假线段数量一共有 $k$ 条，那么答案就是 $f_{k,n}$，时间复杂度为 $O(k\times n)$。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=405,mod=1e9;
struct node{int x,y;};
vector<node> v;
bool cmp(node a,node b){
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}int n,f[N][30],ans;
signed main(){ 
    cin>>n;
    for(int i=1;i<=n;i++) for(int j=1;j<i;j++)  if(__gcd(i,j)==1) v.push_back({j,i});
    sort(v.begin(),v.end(),cmp);
    f[0][1]=1;
    for(int i=1;i<=v.size();i++){
        for(int j=0;j<=n;j++){
            (f[i][j]+=f[i-1][j])%=mod;
            if(v[i-1].x<=j&&j<=v[i-1].y) (f[i][v[i-1].y]+=f[i-1][j])%=mod;
            if(j<v[i-1].x) (f[i][j]+=f[i-1][j])%=mod;
        }
    }cout<<f[v.size()][n];
    return 0;
}