C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 868K, 提交时间: 2019-07-12 10:29:05

#include<bits/stdc++.h>
#define mod 1000000001
#define N 21
using namespace std;
typedef long long ll;
int n;
int a[N][N];
ll f[N][70010];
int vis[100100];
int line[N];
ll calc(int x)
{
    a[1][1]=x;
    int tmp;
    for(int i=1;; i++)
    {
        if(i!=1)
        {
            a[i][1]=a[i-1][1]*2;
            if(a[i][1]>n)
            {
                tmp=i-1;
                break;
            }
        }
        vis[a[i][1]]=1;
        for(int j=2;; j++)
        {
            a[i][j]=a[i][j-1]*3;
            if(a[i][j]>n)
            {
                line[i]=j-1;
                break;
            }
            vis[a[i][j]]=1;
        }
    }
    line[0]=1;
    for(int i=0; i<=tmp; i++)
        for(int j=0; j<(1<<line[i]); j++)
            f[i][j]=0;
    line[tmp+1]=0,f[tmp+1][0]=0;
    f[0][0]=1;
    for(int i=0; i<=tmp; i++)
    {
        for(int j=0; j<(1<<line[i]); j++)
        {
            if(f[i][j])
            {
                if(j&(j>>1))
                    continue;
                for(int k=0; k<(1<<line[i+1]); k++)
                {
                    if(j&k)
                        continue;
                    f[i+1][k]=(f[i+1][k]+f[i][j])%mod;
                }
            }
        }
    }
    return f[tmp+1][0];
}
int main()
{
    scanf("%d",&n);
    ll ans=1;
    for(int i=1; i<=n; i++)
        if(!vis[i])
            ans=ans*calc(i)%mod;
    printf("%lld\n",ans);
}

C++14(g++5.4) 解法, 执行用时: 237ms, 内存消耗: 1144K, 提交时间: 2020-08-19 14:47:07

#include<bits/stdc++.h>
#define Fox ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define turn_on_clock clock_t start,end;start=clock();
#define turn_off_clock end=clock();printf("\nTime eclipse:%.5lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
using namespace std;
const int N=1e5+10;
const int mod=1000000001;
int n,ans=1,v[N];
int num[22],dp[22][4100];
int solve(int x){
	memset(num,0,sizeof(num));
	memset(dp,0,sizeof(dp));
	int cnt=0;
	int tmp=x;
	while(tmp<=n){
		cnt++;
		int c=tmp;
		while(c<=n)num[cnt]++,v[c]=1,c*=3;
		tmp*=2;
	}
	for(int i=0;i<(1<<num[1]);i++)
		if(!((i>>1)&i))dp[0][i]=1;
	int opt=1;
	for(int i=2;i<=cnt;i++,opt=1-opt){
		int Max=(1<<num[i]);
		memset(dp[opt],0,sizeof(dp[opt]));
		for(int j=0;j<Max;j++){
			if((j>>1)&j)continue;
			for(int k=0;k<(1<<num[i-1]);k++)
				if(!(j&k) && !((k>>1)&k))dp[opt][j]=(dp[opt][j]+dp[!opt][k])%mod;
		}
	}
	int rec=0;
	for(int i=0;i<(1<<num[cnt]);i++)
		if(!((i>>1)&i))rec=(rec+dp[!opt][i])%mod;
	return rec;
}
int main(){
	Fox;
	memset(v,0,sizeof(v));
	cin>>n;
	for(int i=1;i<=n;i++)
		if(!v[i])ans=1LL*ans*solve(i)%mod;
	cout<<ans;
	return 0;
}