1 条题解
-
1
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int m,p,s,Ans; char t[105]; struct mat{ int c[32][32]; void clear(){memset(c,0,sizeof(c));} mat operator *(const mat &o)const{ mat r; r.clear(); for(int i=0;i<s;i++) for(int k=0;k<s;k++) for(int j=0;j<s;j++) if(c[i][k]&&o.c[k][j]) r.c[i][j]=(r.c[i][j]+c[i][k]*o.c[k][j])%p; return r; } }f,g; struct BigInt{ int c[105],len; void rad(){ scanf("%s",t); len=strlen(t); for(int i=0;i<len;i++)c[i]=t[i]-48; reverse(c,c+len); } bool pd(){return len>1||c[0];} void div(){ int tmp=0; for(int i=len-1;i>=0;i--){ tmp=tmp*10+c[i]; c[i]=tmp>>1; tmp&=1; } if(!c[len-1])len--; } bool je(){return c[0]&1;} }n; int main(){ n.rad();scanf("%d%d",&m,&p); s=1<<m; for(int i=0;i<s;i++) for(int j=0;j<s;j++){ int tmp=1; for(int k=0;k<m-1;k++){//注意-1 if(((i>>k)&(i>>(k+1))&(j>>k)&(j>>(k+1)))&1){tmp=0;break;}//2*2黑 if(!(((i>>k)|(i>>(k+1))|(j>>k)|(j>>(k+1)))&1)){tmp=0;break;}//2*2白 } g.c[j][i]=tmp; //转移矩阵 } int tmp=0; for(int i=0;i<m;i++)tmp+=(i&1)*(1<<i); f.c[0][tmp]=1;//初始化 黑白黑白 for(;n.pd();n.div(),g=g*g) if(n.je())f=f*g; for(int i=0;i<s;i++)Ans+=f.c[0][i];//累加最后一列所有情况 printf("%d\n",Ans%p); }
- 1
信息
- ID
- 4182
- 时间
- 1000ms
- 内存
- 63MiB
- 难度
- 5
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者