LOJ6485题解

应该是经典题之一了。

\[[n|k]=\frac 1 n\sum_{i=0}^{n-1}w_n^{ik}
\]

有这个就可以算了。

\[\sum_{i=0}^n\binom n i x^ia_{i \mod 4}
\]

按照套路枚举余数

\[\sum_{i=0}^n\binom n ix^i \sum_{k=0}^3 a_k[4|i-k]
\]

\[\frac 1 4\sum_{i=0}^n\binom n ix^i \sum_{k=0}^3 a_k\sum_{j=0}^3w_4^{ij-jk}
\]

\[\frac 1 4\sum_{j=0}^3\sum_{k=0}^3w_4^{-jk}a_k\sum_{i=0}^n\binom n ix^iw_4^{ij}
\]

后面是二项式定理，套起来

\[\frac 1 4\sum_{j=0}^3\sum_{k=0}^3w_4^{-ik}a_k(1+xw_4^j)^n
\]

然后就可以 \(O(\log n)\) 了。

手生疏了，这么短点儿 15min 才推出来/kk

#include<iostream>

#include<cctype>

typedef unsigned ui;

const ui w[]={1,911660635,998244352,86583718},mod=998244353,MOD=mod-1;

ui n,x,a[4],f[4];char buf[1<<21|1],*p=buf;

inline char Getchar(){

	return*p=='\0'&&std::cin.read(p=buf,1<<21),*p++;

}

inline ui read(){

	ui n(0);char s;while(!isdigit(s=Getchar()));while(n=n*10+(s&15),isdigit(s=Getchar()));return n;

}

inline ui readll(){

	ui n(0);char s;while(!isdigit(s=Getchar()));while(n=(n*10ull+(s&15))%MOD,isdigit(s=Getchar()));return n;

}

inline ui pow(ui a,ui b){

	ui ans(1);

	for(;b;b>>=1,a=1ull*a*a%mod)if(b&1)ans=1ull*ans*a%mod;

	return ans;

}

signed main(){

	ui i,j,T,ans;T=read();

	while(T--){

		n=readll();x=read();

		for(i=0;i^4;++i)a[i]=read(),f[i]=pow(1ull*x*w[i]%mod+1,n)%mod;

		ans=(a[0]*(1ull*f[0]+f[1]+f[2]+f[3])+(1ull*a[1]+a[2]+a[3])*f[0]+1ull*a[2]*f[2])%mod;

		ans=(ans+(1ull*a[1]*f[3]+1ull*a[3]*f[1])%mod*911660635ull)%mod;

		ans=(ans+mod-(1ull*a[2]*(f[1]+f[3])+1ull*(a[1]+a[3])*f[2])%mod)%mod;

		ans=(ans+(1ull*a[1]*f[1]+1ull*a[3]*f[3])%mod*86583718ull)%mod;

		printf("%u\n",748683265ull*ans%mod);

	}

}

巴特西

LOJ6485题解

最新文章

热门文章