链接：

题意：

　　给定一个正整数N(1<=N<= 20),表示你每次可以从1到N这些自然数中取两个互质且不同的数出来构成一个数对，例如：N＝5时，你可以取{

{1，2}，{3，4}，{2，5}，{3，5}}等，且数对不能重复。如果存在一个数X（2<=X<=N）,使得每个数对均满足a,b<X 或a,b>=X，则你的取法不合法。例如：你的数对如下{

{1，2}{3，4}}，则X等于3时，这两个数对均满足以上条件，所以方案不合法。计算有多少种合法的取法，答案对1000000000取余。

 

题解：对于一个点对(a,b)，我们将他视为覆盖区间[a,b] 那么问题就转化成了覆盖[1,n]的方案数辣！

 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define MaxN 210#define mod 1000000000using namespace std;int n, N = 0;int x[MaxN], y[MaxN];int f[1<<20];int Solve(){    f[0] = 1;    int top = (1<<(n-1))-1;    for (int i = 1; i <= N; i++){        for (int j = top; j >= 0; j--){            int p = j|(((1<<(y[i]-1))-1)-((1<<(x[i]-1))-1));            f[p] = (f[j]+f[p]) % mod;        }    }     return f[top];}int gcd(int x,int y){    if (!y) return x;    return gcd(y, x%y);}int main(){    freopen("parovi.in", "r", stdin);    freopen("parovi.out", "w", stdout);    scanf("%d", &n);    for (int i = 1; i <= n; i++){        for (int j = i+1; j <= n; j++){            if (gcd(i,j) != 1) continue;            x[++N] = i; y[N] = j;        }    }    cout<