傳送門
l d x ldx ldx又來水水題啦
A n s = ∑ i = 0 n C n i S i a i % 4 = ∑ j = 0 3 a j ∑ i = 0 n C n i S i ∑ k = 0 3 ( ω 4 i − j ) k 4 = 1 4 ∑ j = 0 3 a j ∑ k = 0 3 ω 4 − k j ∑ i = 0 n C n i ( S ω 4 k ) i = 1 4 ∑ j = 0 3 a j ∑ k = 0 3 ω 4 − k j ( S ω 4 k ) n \begin{aligned}Ans=&\sum\limits_{i=0}^nC_n^iS^ia_{i\%4}\\=&\sum\limits_{j=0}^3a_j\sum\limits_{i=0}^nC_n^iS^i\frac{\sum\limits_{k=0}^3(\omega_4^{i-j})^k}4\\=&\frac14\sum\limits_{j=0}^3a_j\sum\limits_{k=0}^3\omega_4^{-kj}\sum_{i=0}^nC_n^i(S\omega_4^k)^i\\=&\frac14\sum\limits_{j=0}^3a_j\sum\limits_{k=0}^3\omega_4^{-kj}(S\omega_4^k)^n\end{aligned} Ans====i=0∑nCniSiai%4j=0∑3aji=0∑nCniSi4k=0∑3(ω4i−j)k41j=0∑3ajk=0∑3ω4−kji=0∑nCni(Sω4k)i41j=0∑3ajk=0∑3ω4−kj(Sω4k)n
然後就做完啦。
代碼：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
typedef long long ll;
inline ll readl(){
ll ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
const int mod=998244353;
int w[4]={1,911660635,998244352,86583718};
inline int add(int a,int b){return (a+=b)<mod?a:a-mod;}
inline int dec(int a,int b){return (a-=b)<0?a+mod:a;}
inline int mul(int a,int b){return (ll)a*b%mod;}
inline void Add(int&a,int b){(a+=b)<mod?a:(a-=mod);}
inline void Dec(int&a,int b){(a-=b)<0?(a+=mod):a;}
inline void Mul(int&a,int b){a=(ll)a*b%mod;}
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,Mul(a,a))if(p&1)Mul(ret,a);return ret;}
int a[4],s,ans,C[105][105];
ll n;
inline void init(){
for(ri i=0;i<=100;++i){
C[i][0]=C[i][i]=1;
for(ri j=1;j<i;++j)C[i][j]=add(C[i-1][j],C[i-1][j-1]);
}
}
int main(){
#ifdef ldxcaicai
freopen("lx.in","r",stdin);
#endif
init();
for(ri t,inv=ksm(4,mod-2),ss,tt=read();tt;--tt){
ans=0;
n=readl()%(mod-1),s=read();
for(ri i=0;i<4;++i)a[i]=read();
for(ri i=0;i<4;++i){
t=ksm(add(1,mul(s,w[i])),n);
ss=0;
for(ri j=0;j<4;++j)Add(ss,mul(a[j],w[(4-i*j%4)%4]));
Add(ans,mul(t,ss));
}
cout<<mul(inv,ans)<<'\n';
}
return 0;
}