fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define mod 1000000000
  5. #define ll long long
  6.  
  7. ll f[25][25], g[25][25];
  8.  
  9. int main() {
  10.    int n;cin>>n;
  11.  
  12.    for(int i=0;i<25;i++)for(int j=0;j<25;j++)f[i][j]=1LL;
  13.  
  14.    for(int i=1;i<=n;i++)
  15.    {
  16.    	for(int j=i+1;j<=n;j++)
  17.    	{
  18.    		if(__gcd(i,j)==1){
  19.    		for(int l=i;l>=1;l--)
  20.    		{
  21.    			for(int r=j;r<=n;r++)f[l][r]<<=1, f[l][r]%=mod;
  22.    		}}
  23.    	}
  24.    }
  25.  
  26.  
  27.  
  28.  
  29.    for(int i=1;i<=n;i++)g[i][i]=1;
  30.  
  31.    for(int l=1;l<=n;l++)
  32.    {
  33.        for(int x=1;x+l<=n;x++)
  34.        {
  35.            int r=x+l;
  36.            g[x][r] = f[x][r];
  37.  
  38.            for(int k=x;k<r;k++)
  39.            {
  40.                g[x][r] -= (g[x][k]*f[k+1][r])%mod;
  41.                g[x][r] = (g[x][r]+mod)%mod;
  42.            }
  43.        }
  44.    }
  45.  
  46.  
  47.  
  48.    cout<<g[1][n]<<endl;
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55. }
Success #stdin #stdout 0s 5532KB
comments (?)
stdin
copy 
5
stdout
copy 
441
https://ideone.com/UZiMt0
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!