题目分析

朋友，你听说过伟达吗？

伟达定理的扩展：若 $x_i$为方程 $x^n+a_1x^{n-1}+a_2x^{n-2}+…+a_{n-1}x+a_n=0$的根，则对于任意 $k \geq n$，令 $S_k=\sum_{i=1}^k x_i^k$，都有 $S_k+a_1S_{k-1}+a_2S_{k-2}+…+a_nS_{k-n}$

啊，多么伟大的定理啊！

有了这个定理，我们就知道 $S_k=-a_1S_{k-1}-a_2S_{k-2}-a_3S_{k-3}-a_4S_{k-4}$，就可以一个矩阵快速幂搞定啦。

但是我们还需要先算出 $S_1$，$S_2$，$S_3$。

把原方程化成 $(x-x_1)(x-x_2)(x-x_3)(x-x_4)=0$的形式，展开得:
$$a=-(x_1+x_2+x_3+x_4)$$
$$b=x_1x_2+x_1x_3+x_1x_4+x_2x_3+x_2x_4+x_3x_4$$
$$c=-(x_1x_2x_3+x_1x_2x_4+x_1x_3x_4+x_2x_3x_4)$$
$$d=x_1x_2x_3x_4$$
那么显然 $S1=-a$
又有 $S2=(x_1+x_2+x_3+x_4)^2-2b$即 $S_2=a^2-2b$
还有 $S3=(x_1+x_2+x_3+x_4)^2-3(-ab+c)$即 $S_3=-a^3+3ab-3c$

啊，多么伟大的定理啊!

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef long long LL;
const int mod=1000000007;
int T;LL n,a,b,c,d;
struct node{LL t[5][5];}x,re;
node operator * (node a,node b) {
    node c;
    for(RI i=1;i<=4;++i)
        for(RI j=1;j<=4;++j) {
            c.t[i][j]=0;
            for(RI k=1;k<=4;++k)
                c.t[i][j]=(c.t[i][j]+a.t[i][k]*b.t[k][j]%mod)%mod;
        }
    return c;
}
LL work() {
    LL S1=-a;
    LL S2=(a*a%mod-2*b%mod)%mod;
    LL S3=(-a*a%mod*a%mod+3*a*b%mod-3*c%mod)%mod;
    if(n==1) return S1;
    if(n==2) return S2;
    if(n==3) return S3;
    for(RI i=1;i<=4;++i)
        for(RI j=1;j<=4;++j) re.t[i][j]=x.t[i][j]=0;
    re.t[1][1]=re.t[2][2]=re.t[3][3]=re.t[4][4]=1;
    x.t[1][1]=-a,x.t[1][2]=-b,x.t[1][3]=-c,x.t[1][4]=-d;
    x.t[2][1]=x.t[3][2]=x.t[4][3]=1;
    for(LL i=n-3;i;i>>=1,x=x*x) if(i&1) re=re*x;
    LL k=S3*re.t[1][1]%mod+S2*re.t[1][2]%mod+S1*re.t[1][3]%mod+4*re.t[1][4]%mod;
    return k%mod;
}
void print(LL x) {
    x%=mod;while(x<0) x+=mod;
    printf("%lld\n",x);
}
int main()
{
    scanf("%d",&T);
    while(T--) {
        scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d);
        print(work());
    }
    return 0;
}