LOJ6485

LJJ 学二项式定理

直接单位根反演。

$$\begin{array}{rl}& \sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})s^i{a}_{imod4}\\ =& \sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})s^i\sum _{j=0}^3{a}_j[i\equiv j(\mathrm{mod}4)]\\ =& {\displaystyle \frac{1}{4}}\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})s^i\sum _{j=0}^3{a}_j\sum _{k=0}^3{\omega }_4^{(i-j)k}\\ =& {\displaystyle \frac{1}{4}}\sum _{j=0}^3{a}_j\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})s^i\sum _{k=0}^3{\omega }_4^{ki}{\omega }_4^{-kj}\\ =& {\displaystyle \frac{1}{4}}\sum _{j=0}^3{a}_j\sum _{k=0}^3{\omega }_4^{-kj}\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})s^i{\omega }_4^{ki}\\ =& {\displaystyle \frac{1}{4}}\sum _{j=0}^3{a}_j\sum _{k=0}^3{\omega }_4^{-kj}\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})(s{\omega }_4^k{)}^i{1}^{n-i}\\ =& {\displaystyle \frac{1}{4}}\sum _{j=0}^3{a}_j\sum _{k=0}^3{\omega }_4^{-kj}(s{\omega }_4^k+1{)}^n\end{array}$$

拿原根直接算就完了。时间复杂度 $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;
}