首页 > 代码库 > hdu4602（矩阵快速幂）
hdu4602（矩阵快速幂）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4602
题意：对于每个数的分解，列出其元素的出现的个数。
1 2 3 4 5
1 1 2 5 12 28
2 1 2 5 12
3 1 2 5
4 1 2
5 1
所以数列符合a_1 = 1, 2, 5, 12, 28 。。。。。a_n = 2*f(n-1)+2^(n-3)
由上面公式可构造矩阵：
|2,1,0|
|a[n-1],a[n-2],2^(n-3)|=|0,0,0|=|a[n],a[n-1],2^(n-2)|
|1,0,2|
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 40010#define clr(a) (memset(a,0,sizeof(a)))using namespace std;struct matrix{ LL m[3][3];};matrix mult(matrix a,matrix b){ matrix c; memset(c.m,0,sizeof(c.m)); for(int i=0;i<3;i++) for(int j=0;j<3;j++) { if(a.m[i][j]==0)continue; for(int k=0;k<3;k++) { if(b.m[j][k]==0)continue; c.m[i][k]+=a.m[i][j]*b.m[j][k]%mod; c.m[i][k]%=mod; } } return c;}matrix quickmod(matrix a,int n){ matrix temp; memset(temp.m,0,sizeof(temp.m)); for(int i=0;i<=2;i++)temp.m[i][i]=1; while(n) { if(n&1)temp=mult(temp,a); a=mult(a,a); n/=2; } return temp;}int main(){ int n,k,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); n=n-k+1; if(n<=2) { if(n<=0)puts("0"); else if(n==1)puts("1"); else if(n==2)puts("2"); continue; } matrix ans; ans.m[0][0]=2;ans.m[0][1]=1;ans.m[0][2]=0; ans.m[1][0]=0;ans.m[1][1]=0;ans.m[1][2]=0; ans.m[2][0]=1;ans.m[2][1]=0;ans.m[2][2]=2; ans=quickmod(ans,n-2); //a[n]=a[2]*ans.m[0][0]+a[1]*0+2^(3-3)*ans.m[2][0] printf("%d\n",(ans.m[0][0]*2+ans.m[2][0])%mod); }}
hdu4602（矩阵快速幂）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。