本文共 2077 字，大约阅读时间需要 6 分钟。
做这个题之前你的知道一元四次方程的求根公式（为什么我的小学体育老师没教过我...）
设x^4+ax^3+bx²+cx+d=0的四个根是x1,x2,,x4,则 x1+x2++x4=﹣a x1x2+x1+x1x4+x2x3+x2x4+x3x4=b x1x2x3+x1x2x4+x1x3x4+x2x3x4=﹣c x1x2x3x4=d然后你可以通过推导得到x1^2+x2^2+x3^2+x4^2,x1^3+x2^3+x3^3+x4^3
设答案是f(n)
那么f(n+1)=-a*f(n)-b*f(n-1)-c*f(n-2)-d*f(n-3)
构造矩阵，然后快速幂加速就好了。
d*f(n-3)还是需要注意下的，一步小心就写成d*4就不对了，常数项的本质其实是x^0的系数，或者你再写下f（5）是怎么得到的也能发现不对。
代码：
#include#define LL long long using namespace std;const int mod=1e9+7;struct matrix{ LL rec[6][6]; void init() { for(int i=0; i<4; i++)memset(rec[i], 0, sizeof rec[i]); } void MOD() { for(int i=0; i<4; i++) { for(int j=0; j<4; j++) { rec[i][j]=(rec[i][j]%mod+mod)%mod; } } return; }};matrix operator *(const matrix & a, const matrix & b){ matrix res; res.init(); int i, j, k; for(i=0; i<4; i++) { for(j=0; j<4; j++) { for(k=0; k<4; k++) { res.rec[i][j]=(res.rec[i][j]+(a.rec[i][k]*b.rec[k][j])%mod)%mod; res.rec[i][j]=(res.rec[i][j]%mod+mod)%mod; } } } return res;}matrix rec_mod(matrix a, LL n){ matrix base=a, res; res.init(); for(int i=0; i<4; i++)res.rec[i][i]=1; while(n) { if(n&1)res=res*base; n>>=1; base=base*base; } return res;}int main(){ int t, i, j; LL a ,b ,c, d; LL n; matrix pow, ans; cin>>t; while(t--) { scanf("%lld", &n); scanf("%lld%lld%lld%lld", &a, &b, &c, &d); pow.init(); pow.rec[0][0]=-a, pow.rec[0][1]=1; pow.rec[1][0]=-b, pow.rec[1][2]=1; pow.rec[2][0]=-c, pow.rec[2][3]=1; pow.rec[3][0]=-d; ans.init(); ans.rec[0][3]=4, ans.rec[0][2]=-a, ans.rec[0][1]=(a*a)%mod-2*b, ans.rec[0][0]=-(((a*a)%mod)*a)%mod+3*(a*b)%mod-3*c; ans.MOD(); pow.MOD(); if(n<=3) { printf("%lld\n", ans.rec[0][3-n]); continue; } pow=rec_mod(pow, n-3); ans=ans*pow; printf("%lld\n", ans.rec[0][0]); }}
转载地址：http://loywb.baihongyu.com/