状态压缩加矩阵。
状态压缩的思想和前面几道状态压缩的题一样的,没的说。但是矩阵为什么可以快速幂非常疑惑不解。。。。。嗯,,因为这道题的数据大,所以要用一个矩阵来递推。
刚开始的时候把记录结果的那个矩阵地对角线给标为一了,现在我认为是因为为了要记录能从pre推到now的状态总数。但是不懂为什么到后来是要相乘。然后不懂为什么每次当k推到奇数的时候才进行记录。。。。
这里先mark一下。
************************************************
诶。。。当初我看矩阵快速幂的时候是有多散漫啊,这次看别人的代码一点没看出来只是一个快速幂,,,还以为里面还有什么玄机。。。。。擦咧。。。。
好忧伤。。。。。。。然后我还没看出来那个对角线是1 的矩阵叫做。。。单位矩阵。。。。呵呵了。。。。
贴代码。。跑了63ms。。。。嗯。。。。
刚开始wa了好多次,,为什么呢呢。。。。谨遵队友指示不敢对拍了,不过第一发现是自己对于矩阵乘法的剪枝还不熟,所以这里用的是纯土法。然后,,,本来我使用n本尊进行快速幂的,然后,,把它换成k来替代就过了,,诶,,,高冷的n。。。
为毛啊。。。
#include <stdio.h> #include <string.h> #define ll __int64 int n,m; struct node { ll a[16][16]; }mat; void dfs(int d,int now,int pre) { if(d>4) return; if(d==4) { ++mat.a[pre][now]; return; } dfs(d+1,now<<1|1,pre<<1); dfs(d+1,now<<1,pre<<1|1); dfs(d+2,now<<2|3,pre<<2|3); } struct node mul(node x,node y) { int i,j,k; node z; memset(z.a,0,sizeof(z.a)); for(i=0;i<16;i++) { for(j=0;j<16;j++) { for(k=0;k<16;k++) z.a[i][j]+=x.a[i][k]*y.a[k][j]%m; z.a[i][j]%=m; } } return z; } struct node solve(node x) { if(n==1) return x; node tmp; memset(tmp.a,0,sizeof(tmp.a)); int i,j,k; for(i=0;i<16;i++) tmp.a[i][i]=1; k=n; while(k) { if(k&1) tmp=mul(x,tmp); x=mul(x,x); k>>=1; } return tmp; } int main() { memset(mat.a,0,sizeof(mat.a)); dfs(0,0,0); while(scanf("%d%d",&n,&m)!=EOF&&n+m) { node ans; if(m==1) {printf("0\n");continue;} ans=solve(mat); printf("%I64d\n",ans.a[15][15]); } return 0; }