首页 > 代码库 > hdu_5950_Recursive sequence(矩阵快速幂)
hdu_5950_Recursive sequence(矩阵快速幂)
题目链接:hdu_5950_Recursive sequence
题意:递推求解:F(n) = 2*F(n-2) + F(n-1) + n4 和F(1) = a,F(2) = b;
题解:
一看数据范围,肯定矩阵加速递推,不过公式不是线性的,需要把公式转换为线性的公式
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4 typedef long long ll; 5 6 const int mat_N=7; 7 ll mo=2147493647; 8 9 struct mat{ 10 ll c[mat_N][mat_N]; 11 void init(){memset(c,0,sizeof(c));} 12 mat operator*(mat b){ 13 mat M;int N=mat_N-1;M.init(); 14 F(i,0,N)F(j,0,N)F(k,0,N)M.c[i][j]=(M.c[i][j]+c[i][k]*b.c[k][j])%mo; 15 return M; 16 } 17 mat operator^(ll k){ 18 mat ans,M=(*this);int N=mat_N-1;ans.init(); 19 F(i,0,N)ans.c[i][i]=1; 20 while(k){if(k&1)ans=ans*M;k>>=1,M=M*M;} 21 return ans; 22 } 23 }A,B,C; 24 25 int t,n,a,b; 26 27 int main() 28 { 29 scanf("%d",&t); 30 while(t--) 31 { 32 scanf("%d%d%d",&n,&a,&b); 33 A=(mat){0,1,0,0,0,0,0, 34 2,1,1,4,6,4,1, 35 0,0,1,4,6,4,1, 36 0,0,0,1,3,3,1, 37 0,0,0,0,1,2,1, 38 0,0,0,0,0,1,1, 39 0,0,0,0,0,0,1}; 40 C=A^(n-2); 41 ll ans=0; 42 ans=(C.c[1][0]*a+C.c[1][1]*b+C.c[1][2]*16+C.c[1][3]*8+C.c[1][4]*4+C.c[1][5]*2+C.c[1][6])%mo; 43 printf("%lld\n",ans); 44 } 45 return 0; 46 }
hdu_5950_Recursive sequence(矩阵快速幂)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。