分析：
构造法...每次找到一个没有被选过的数，用这个数推出一个表格，之后在表格上跑状压DP，时间复杂度O（n）
附上代码：
#include#include #include #include #include #include #include using namespace std;#define N 25#define M 1<<11#define mod 1000000001int f[N][M],a[N][N],b[N],K,n,m,vis[1000005];long long ans=1;int calc(int t){ memset(b,0,sizeof(b)); a[1][1]=t; for(int i=2;i<=18;i++) { a[i][1]=a[i-1][1]<<1; if(a[i][1]>n)a[i][1]=n+1; } for(int i=1;i<=18;i++) { for(int j=2;j<=11;j++) { a[i][j]=a[i][j-1]*3; if(a[i][j]>n)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]+=(1<<(j-1)); vis[a[i][j]]=1; } } } for(int i=0;i<=18;i++) { for(int S=0;S<=b[i];S++) { f[i][S]=0; } } f[0][0]=1; for(int i=1;i<=18;i++) { for(int S=0;S<=b[i-1];S++) { if(!f[i-1][S])continue; for(int s=0;s<=b[i];s++) { if((S&s)||(s&(s<<1)))continue; f[i][s]=(f[i][s]+f[i-1][S])%mod; } } } return f[18][0];}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { if(!vis[i]) { ans=(ans*calc(i))%mod; } } printf("%lld\n",ans); return 0;}