题意：
给出一个表达式 fn= fn-1 + 2*f(n-2 ) +n^4
思路：
重点在于n^4 的拆解，如何可以拆解为n-1的若干项的形式，可以考虑用二项式展开来拆解，也就是将n^4 拆解为 ((n-1)+1)^4,之后C(4,0)(n-1)^4+C(4,1)(n-1)^3如此即可
#include <iostream> #include <stdlib.h> #include <string.h> #include <stdio.h> #include <queue> using namespace std; typedef long long ll; ll n,m; const int maxn=8; const ll mod=2147493647; struct Matrix//矩阵的类 { ll a[maxn][maxn]; void init() //将其初始化为单位矩阵 { memset(a,0,sizeof(a)); for(int i=1;i<maxn;i++) a[i][i]=1; } } ; Matrix mul(Matrix a,Matrix b) //(a*b)%mod 矩阵乘法 { Matrix ans; memset(ans.a,0,sizeof(ans.a)); for(int i=1;i<maxn;i++) { ans.a[i][i]=1; } for(int i=1;i<maxn;i++) for(int j=1;j<maxn;j++) { ans.a[i][j]=0; for(int k=1;k<maxn;k++) ans.a[i][j]+=a.a[i][k]*b.a[k][j]%mod; ans.a[i][j]%=mod; } return ans; } Matrix pow(Matrix a) { Matrix res ; memset(res.a,0,sizeof(res.a)); for(int i=1;i<maxn;i++) { res.a[i][i]=1; } while(n) { if(n&1) { res=mul(a,res); } a=mul(a,a); n/=2; } return res; } int main() { int t; scanf("%d",&t); while(t--) { ll a,b; scanf("%lld%lld%lld",&n,&a,&b); Matrix ans; ans.a[1][1]=b,ans.a[2][1]=a,ans.a[3][1]=16,ans.a[4][1]=8,ans.a[5][1]=4,ans.a[6][1]=2,ans.a[7][1]=1; Matrix base,res; ll sss[8][8]={ {0,0,0,0,0,0,0,0}, {0,1,2,1,4,6,4,1}, {0,1,0,0,0,0,0,0}, {0,0,0,1,4,6,4,1}, {0,0,0,0,1,3,3,1}, {0,0,0,0,0,1,2,1}, {0,0,0,0,0,0,1,1}, {0,0,0,0,0,0,0,1}}; for(int i=0;i<=7;i++) { for(int j=0;j<=7;j++) base.a[i][j]=sss[i][j]; } if(n==1) { printf("%lld\n",a); } else if(n==2) { printf("%lld\n",b); } else { n=n-2; res=pow( base ); ans=mul(res,ans); printf("%lld\n",ans.a[1][1]); } } }