LOJ6485

LJJ 学二项式定理

直接单位根反演。

$$
\begin{aligned}
& \sum _ {i = 0 } ^ {n} \binom {n} {i} s ^ {i} a _{ i \bmod 4 }
\\
= & \sum _ { i = 0 } ^ {n} \binom {n} {i} s ^ {i} \sum _ {j=0} ^ {3} a _ j [ i \equiv j \pmod { 4 } ]
\\
= & \dfrac {1} {4} \sum _ { i = 0 } ^ {n} \binom {n} {i} s ^ {i} \sum _ { j = 0 } ^ {3} a _ j \sum _ { k = 0 } ^ {3} \omega _ {4} ^ { ( i - j ) k }
\\
= & \dfrac {1} {4} \sum _ { j = 0 } ^ { 3 } a _ j \sum _ { i = 0 } ^ {n} \binom { n } { i } s ^ i \sum _ { k = 0 } ^ { 3 } \omega _ {4} ^ {ki} \omega _ { 4 } ^ { - k j }
\\
= & \dfrac {1} {4} \sum _ { j = 0 } ^ { 3 } a _ j \sum _ { k = 0 } ^ { 3 } \omega _ { 4 } ^ { - k j }\sum _ { i = 0 } ^ {n} \binom { n } { i } s ^ i \omega _ {4} ^ {ki}
\\
= & \dfrac {1} {4} \sum _ { j = 0 } ^ { 3 } a _ j \sum _ { k = 0 } ^ { 3 } \omega _ { 4 } ^ { - k j }\sum _ { i = 0 } ^ {n} \binom { n } { i } ( s \omega _ {4} ^ {k} ) ^ i 1 ^ { n - i }
\\
= & \dfrac {1} {4} \sum _ { j = 0 } ^ { 3 } a _ j \sum _ { k = 0 } ^ { 3 } \omega _ { 4 } ^ { - k j } ( s \omega _ { 4 } ^ { k } + 1 ) ^ n
\end{aligned}
$$

拿原根直接算就完了。时间复杂度 $O(\log n)$。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}

const ll mo=998244353,G=3;

inline ll Pow(ll b,ll p) {
  ll r=1;while(p) {if(p&1) r=r*b%mo;b=b*b%mo;p>>=1;}return r;
}

const ll invG=Pow(G,mo-2);

ll a[5];

int main() {

  ll T;T=read();
  while(T--) {
    ll n,s;
    n=read();s=read();a[0]=read();a[1]=read();a[2]=read();a[3]=read();
    ll ans=0;
    ll tG=Pow(G,(mo-1)/4),mG=Pow(invG,(mo-1)/4);
    for(ll j=0;j<4;j++) {
      ll tmpp=0;
      for(ll i=0;i<4;i++) {
        tmpp=(tmpp+Pow(mG,i*j)*Pow((s*Pow(tG,i)%mo+1)%mo,n)%mo)%mo;
      }
      tmpp=tmpp*a[j]%mo;
      ans=(ans+tmpp)%mo;
    }
    ans=ans*Pow(4,mo-2)%mo;
    writeln(ans);
  }

  return 0;
}