C++11(clang++ 3.9) 解法, 执行用时: 21ms, 内存消耗: 496K, 提交时间: 2019-03-05 21:13:01

#include<bits/stdc++.h>
typedef unsigned int u32;
typedef u32 mat[57][57];
const u32 P=65521;
mat c,x,y;
int N,k;
long long n;
inline u32 fix(u32 x){
    return x-(x>>16)*P;
}
void clr(mat a,u32 v){
    for(int i=1;i<=N;a[i][i]=v,++i)
    for(int j=1;j<=N;++j)
        a[i][j]=0;
}
void mul(mat a,mat b){
    clr(c,0);
    for(int i=1;i<=N;++i)
    for(int k=1;k<=N;++k)if(a[i][k])
    for(int j=1;j<=N;++j)
        c[i][j]+=fix(a[i][k]*b[k][j]);
    for(int i=1;i<=N;++i)
    for(int j=1;j<=N;++j)
        a[i][j]=c[i][j]%P;
}
int ids[33333],idp=0;
int tr[57][32],st[57],f[11],g[7][57],ed[11];
void dfs(int w,int m,int v){
    if(w==k){
        ids[v]=++idp;
        st[idp]=v;
        return;
    }
    for(int i=0;i<=m;++i)dfs(w+1,m+(i==m),v|i<<3*w);
}
void upd(int k){
    for(int i=0;i<k;++i)ed[i]=-1;
    for(int i=0,p=0;i<k;++i){
        if(ed[f[i]]<0)ed[f[i]]=p++;
        f[i]=ed[f[i]];
    }
}
void mg(int a,int b,int k){
    int z=f[b];
    for(int i=0;i<k;++i)if(f[i]==z)f[i]=f[a];
}
int main(){
    scanf("%d%lld",&k,&n);
    dfs(0,0,0);
    N=idp;
    for(int i=1;i<=idp;++i){
        for(int j=0,ab;j<(1<<k);++j){
            for(int a=0;a<k;++a)f[a]=st[i]>>a*3&7;
            ab=1;
            for(int a=0,pv=-1;a<k;++a)if(j>>a&1){
                if(pv<0)pv=a;
                else if(f[pv]==f[a])ab=0;
                else mg(pv,a,k);
            }
            if(ab){
                upd(k);
                int v=0;
                for(int a=0;a<k;++a)v|=f[a]<<a*3;
                tr[i][j]=ids[v];
            }
            
            for(int a=0;a<k;++a)f[a]=st[i]>>a*3&7;
            f[k]=k;
            ab=1;
            for(int a=0,pv=-1;a<k;++a)if(j>>a&1){
                if(f[k]==f[a])ab=0;
                else mg(k,a,k+1);
            }
            if(ab){
                ab=0;
                for(int i=1;i<=k;++i)ab|=f[0]==f[i];
                if(ab){
                    for(int i=0;i<k;++i)f[i]=f[i+1];
                    upd(k+1);
                    int v=0;
                    for(int a=0;a<k;++a)v|=f[a]<<a*3;
                    ++y[ids[v]][i];
                }
            }
        }
    }
    g[1][idp]=1;
    for(int t=1;t<k;++t){
        int L=1<<t,R=L<<1;
        for(int i=1;i<=idp;++i)if(g[t][i]){
            for(int j=L;j<R;++j){
                (g[t+1][tr[i][j]]+=g[t][i])%=P;
            }
        }
    }
    clr(x,1);
    for(n-=k;n;n>>=1,mul(y,y))if(n&1)mul(x,y);
    int ans=0;
    for(int i=1;i<=idp;++i)ans+=fix(x[1][i]*g[k][i]);
    printf("%d\n",ans%P);
    return 0;
}