zcmimi's blog

查看原题

点击跳转

x构造一个矩阵满足a(i,j+1)=2a(i,j),a(i+1,j)=3a(i,j)

对于这个矩阵,我们不能选相邻的数,也就是说答案为不选相邻的数的方案数

这个矩阵长\log_2 n(不超过17),宽\log_3 n(不超过12),因此可以用状压dp解决

我们只需要对不是2,3倍数的数都构造一个矩阵就可以覆盖所有的数,容易发现每个矩阵互不相同,所以根据乘法原理把答案相乘即可

#include<bits/stdc++.h>
const int P=1000000001;
int T,a[18][18],f[18][1<<18],lim[18];
bool b[1<<18];
int solve(int x){
    int n,i,j,k,ans=0;
    for(n=1;x<=T;++n,x*=3)
        lim[n]=2<<(int)log2(T/x);
    --n;
    for(i=0;i<lim[1];++i)f[1][i]=b[i];
    for(i=2;i<=n;++i)
        for(j=0;j<lim[i];++j)if(b[j])
            for(f[i][j]=k=0;k<lim[i-1];++k)if(b[k]&&!(j&k))
                (f[i][j]+=f[i-1][k])%=P;
    for(int i=0;i<lim[n];++i)(ans+=f[n][i])%=P;
    return ans;
}
int main(){
    scanf("%d",&T);
    for(int i=0;i<1<<18;++i)b[i]=!(i&(i<<1));
    int ans=1;
    for(int i=1;i<=T;++i)
        if(i%2&&i%3)ans=1ll*ans*solve(i)%P;
    printf("%d\n",ans);
}
LG 3226 [HNOI2012]集合选数
comment评论
Search
search