首页 > 代码库 > [矩阵快速幂] fzu 2117 特殊的数
[矩阵快速幂] fzu 2117 特殊的数
题意:
中文题不解释
注意是n位数!
思路:
中文在群里问了大神们,终于领悟到这种递推的精华
对于给定的n都会包含有四种状态
0、7和9的个数都是奇数
1、7是奇数,9是偶数
2、7是偶数,9是奇数
3、7是偶数,9是偶数
显然状态3是我们要状态,但是他们之间是可以互相转移的
所以对于每次添加一个空位放数字,建立转移矩阵
| 3 1 1 0 |
| 1 3 0 1 |
| 1 0 3 1 |
| 0 1 1 3 |
初始状态为 (0,0,0,1)
然后就是n次方了~利用矩阵快速幂
最后ans.mat[0][3]就是答案了
代码:
#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"queue" #include"algorithm" #include"iostream" using namespace std; __int64 mod=1000000007; struct matrix { __int64 mat[5][5]; }; matrix matmul(matrix a,matrix b,int n,int m) { int i,j,k; matrix c; memset(c.mat,0,sizeof(c.mat)); for(i=0;i<n;i++) { for(j=0;j<n;j++) { for(k=0;k<n;k++) { 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,int 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() { int t; cin>>t; while(t--) { matrix a,b,ans; memset(a.mat,0,sizeof(a.mat)); memset(b.mat,0,sizeof(b.mat)); a.mat[0][3]=1; for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { if(i==j) b.mat[i][j]=3; else if(i+j==3) b.mat[i][j]=0; else b.mat[i][j]=1; } } __int64 k; scanf("%I64d",&k); ans=matmul(a,matpow(b,k,4,mod),4,mod); __int64 sum=0; printf("%I64d\n",ans.mat[0][3]); } return 0; }
[矩阵快速幂] fzu 2117 特殊的数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。