首页 > 代码库 > [矩阵快速幂] hdu 3893 Drawing Pictures
[矩阵快速幂] hdu 3893 Drawing Pictures
题意:
给长度N的格子,有六种颜料ABCDEF,
要求涂满N个格子的方案数,并且保证是对称的,并且相邻的格子颜色不同,并且不出现ABCDEF这个序列。
思路:
受到中午那题,思维大开
首先因为颜色相邻不能相同且要对称,所以N为偶数答案为0.
接着先假设有这六种状态0(代表没颜色限制),A,AB,ABC,ABCD,ABCDE
然后初始状态为(5,1,0,0,0,0)两两之间构成转换关系
结果提交WA了
发现这题真是丧心病狂
如果是这样FEDCBABCDEF 这样对称的话就会跪
所以还有5个状态 F,FE,FED,FEDC,FEDCB
总共11个状态互相转换
注意之间的转换关系就好了
所以初始的是(4,1,0,0,0,0,1,0,0,0,0)
转换矩阵是
3 1 0 0 0 0 1 0 0 0 0
3 0 1 0 0 0 1 0 0 0 0
2 1 0 1 0 0 1 0 0 0 0
2 1 0 0 1 0 1 0 0 0 0
2 1 0 0 0 1 1 0 0 0 0
3 1 0 0 0 0 0 0 0 0 0
3 1 0 0 0 0 0 1 0 0 0
2 1 0 0 0 0 1 0 1 0 0
2 1 0 0 0 0 1 0 0 1 0
2 1 0 0 0 0 1 0 0 0 1
3 0 0 0 0 0 1 0 0 0 0
然后最后ans.mat[0][0~10]求和一下就是答案啊了~!
代码:
#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"queue" #include"algorithm" #include"iostream" using namespace std; __int64 mod=112233; struct matrix { __int64 mat[13][13]; }; matrix matmul(matrix a,matrix b,int n,__int64 m) { int i,j,k; matrix c; memset(c.mat,0,sizeof(c.mat)); for(i=0; i<n; i++) { for(k=0; k<n; k++) { for(j=0; j<n; j++) { c.mat[i][j]+=a.mat[i][k]*b.mat[k][j]; c.mat[i][j]%=m; } } } return c; } matrix matpow(matrix a,__int64 k,int n,__int64 m) { matrix b; int i; memset(b.mat,0,sizeof(b.mat)); for(i=0; i<n; i++) b.mat[i][i]=1; while(k) { if(k&1) b=matmul(a,b,n,m); a=matmul(a,a,n,m); k>>=1; } return b; } int main() { __int64 n; while(scanf("%I64d",&n)!=-1) { if(n%2==0) { puts("0"); continue; } matrix a,b,ans; memset(a.mat,0,sizeof(a.mat)); memset(b.mat,0,sizeof(b.mat)); a.mat[0][0]=4; a.mat[0][1]=a.mat[0][6]=1; b.mat[0][0]=b.mat[1][0]=b.mat[5][0]=b.mat[6][0]=b.mat[10][0]=3; for(int i=0;i<11;i++) { if(b.mat[i][0]==0) b.mat[i][0]=2; } for(int i=0;i<10;i++) b.mat[i][i+1]=1; for(int i=2;i<10;i++) b.mat[i][1]=1; for(int i=0;i<11;i++) { if(i!=6) b.mat[i][6]=1; } b.mat[5][6]=0; ans=matmul(a,matpow(b,n/2,11,mod),11,mod); __int64 sum=0; for(int i=0;i<11;i++) sum=(sum+ans.mat[0][i])%mod; printf("%I64d\n",sum); } return 0; }
[矩阵快速幂] hdu 3893 Drawing Pictures
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。