Problem

https://www.luogu.org/problemnew/show/P3226

Solution

题解太多了不讲了。

相信自己的实现，做了一些有 (luan) 趣(gao)的优化能跑得很快。

// Code by ajcxsu
// Problem: set num

#include<bits/stdc++.h>
#define MOD (1000000001ll)
using namespace std;

typedef long long ll;
const int N=1e5+10;
int arr[N];
ll mat[20][20];
int po[40];
int r=18, c=12;
ll f[18][1<<12];
int U=1<<c;
int n;

ll work() {
    ll ret=0;
    int j, T;
    for(int i=0;i<r && mat[i][0]<=n;i++) {
        ret=0;
        for(j=0, T=1; mat[i][j]<=n; j++, T<<=1);
        U=T<<1;
        for(int j=0;j<U;j++) f[i][j]=0;
        for(int j=0;j<T;j++) {
            if(!(j&(j<<1))) {
                if(!i) f[i][j]=1;
                else {
                    for(int k=U-1-j;k;k=(U-1-j)&(k-1))
                        (f[i][j]+=f[i-1][k])%=MOD;
                    (f[i][j]+=f[i-1][0])%=MOD;
                }
            }
            ret+=f[i][j];
        }
    }
    return ret%=MOD;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    po[0]=1;
    for(int i=1;i<20;i++) po[i]=po[i-1]*3;
    cin>>n;
    ll ans=1;
    for(int i=1;i<=n;i++) {
        if(!arr[i]) {
            mat[0][0]=i;
            for(int j=0;j<r;j++)
            for(int k=0;k<c;k++) {
                mat[j][k]=1ll*i*(1<<j)*po[k];
                if(mat[j][k]>=1 && mat[j][k]<N) arr[mat[j][k]]=1;
            }
            ans=ans*work()%MOD;
        }
    }
    printf("%lld\n", ans);
    return 0;
}