来源: 集合选数 – HYSBZ 2734 – Virtual Judge
代码
#include <iostream> #include <bits/stdc++.h> using namespace std; #define mod 1000000001 #define inf 0x3f3f3f3f #define ll long long int bin[20],n; ll ans=1; int a[22][22],b[22],f[22][2048]; bool vis[100010]; int cal(int x) { memset(b,0,sizeof(b)); a[1][1]=x; for(int i=2;i<=18;i++) { if(a[i-1][1]*2<=n) a[i][1]=a[i-1][1]*2; else a[i][1]=n+1; } for(int i=1;i<=18;i++) { for(int j=2;j<=11;j++) { if(a[i][j-1]*3<=n) a[i][j]=a[i][j-1]*3; else a[i][j]=n+1; } } for(int i=1;i<=18;i++) { for(int j=1;j<=11;j++) { if(a[i][j]<=n) { b[i]+=bin[j-1]; vis[a[i][j]]=1; } } } for(int i=1;i<=18;i++) { for(int x=0;x<=b[i];x++) { f[i][x]=0; } } f[0][0]=1; for(int i=0;i<18;i++) { for(int x=0;x<=b[i];x++) { if(f[i][x]) { for(int y=0;y<=b[i+1];y++) { if(((x&y)==0)&&((y&(y>>1))==0)) { f[i+1][y]=(f[i][x]+f[i+1][y])%mod; } } } } } return f[18][0]; } int main() { bin[0]=1; for(int i=1;i<20;i++)//预处理2的i次幂 { bin[i]=bin[i-1]*2; } cin>>n; for(int i=1;i<=n;i++) { if(!vis[i]) { ans=(ans*cal(i))%mod; } } cout<<ans<<endl; return 0; }