[LOJ 6485]LJJ学二项式定理(单位根反演)

也许更好的阅读体验

$Description$Description

原题链接

$T$T组询问，每次给 $n,s,a_0,a_1,a_2,a_3$n,s,a0​,a1​,a2​,a3​求
$\begin{array}{c}{\displaystyle (\sum _{i=0}^n\left(\begin{array}{c}n\\ i\end{array}\right)\cdot s^i\cdot a_{imod4})mod998244353}\end{array}$(i=0∑n​(ni​)⋅si⋅ai mod 4​)mod 998244353​

$Solution$Solution

这道题要用单位根反演
$\begin{array}{c}{\displaystyle \left[n\mid k\right]=\frac{1}{n}\sum _{i=0}^{n-1}{w}_n^{ik}}\end{array}$[n ∣ k]=n1​i=0∑n−1​wnik​​

我们先打表，或者查表找出在模 $998244353$998244353下的原根 ${\omega }_4^0$ω40​并处理好 ${\omega }_4^1,{\omega }_4^2,{\omega }_4^3$ω41​,ω42​,ω43​
考虑对每个 $a_i$ai​单独计算其答案
以 $a_0$a0​为例
$\begin{array}{cc}{\displaystyle an{s}_{a_0}}& {\displaystyle =\frac{1}{4}{a}_0\sum _{i=0}^n\left[4\mid i\right]\left(\frac{n}{i}\right)s^i}\\ {\displaystyle }& {\displaystyle =\frac{1}{4}{a}_0\sum _{i=0}^n\left(\frac{n}{i}\right)s^i\sum _{j=0}^3({\omega }_4^j{)}^i}\\ {\displaystyle }& {\displaystyle =\frac{1}{4}{a}_0\sum _{j=0}^3\sum _{i=0}^n\left(\frac{n}{i}\right)s^i({\omega }_4^j{)}^i}\\ {\displaystyle }& {\displaystyle =\frac{1}{4}{a}_0\sum _{j=0}^3(s{\omega }_4^j+1{)}^n}\end{array}$ansa0​​​=41​a0​i=0∑n​[4 ∣ i](in​)si=41​a0​i=0∑n​(in​)sij=0∑3​(ω4j​)i=41​a0​j=0∑3​i=0∑n​(in​)si(ω4j​)i=41​a0​j=0∑3​(sω4j​+1)n​

对于其他 $a_i$ai​，我们可以将其写成 $[4\mid i+4-k]$[4 ∣ i+4−k]的形式，并提一个 ${\omega }^x$ωx出来
下面完整的推一遍

$\begin{array}{cc}{\displaystyle ans}& {\displaystyle =\sum _{k=0}^3{a}_k\sum _{i=0}^n[4\mid i+4-k]s^i\cdot \left(\begin{array}{c}n\\ i\end{array}\right)}\\ {\displaystyle }& {\displaystyle =\sum _{k=0}^3\frac{1}{4}{a}_k\sum _{i=0}^n\sum _{j=0}^3{\omega }_4^{j\cdot (i+4-k)}\cdot s^i\cdot \left(\begin{array}{c}n\\ i\end{array}\right)}\\ {\displaystyle }& {\displaystyle =\sum _{k=0}^3\frac{1}{4}{a}_k\sum _{i=0}^n\sum _{j=0}^3{\omega }_4^{(4j-jk)}\cdot {\omega }_4^{j^i}\cdot s^i\cdot \left(\begin{array}{c}n\\ i\end{array}\right)}\\ {\displaystyle }& {\displaystyle =\sum _{k=0}^3\frac{1}{4}{a}_k\sum _{j=0}^3{\omega }_4^{(4j-jk)}\sum _{i=0}^n{\omega }^{j^i}\cdot s^i\cdot \left(\begin{array}{c}n\\ i\end{array}\right)}\\ {\displaystyle }& {\displaystyle =\sum _{k=0}^3\frac{1}{4}{a}_k\sum _{j=0}^3{\omega }_4^{(4j-jk)}{(s\cdot {\omega }_4^j+1)}^n}\end{array}$ans​=k=0∑3​ak​i=0∑n​[4 ∣ i+4−k]si⋅(ni​)=k=0∑3​41​ak​i=0∑n​j=0∑3​ω4j⋅(i+4−k)​⋅si⋅(ni​)=k=0∑3​41​ak​i=0∑n​j=0∑3​ω4(4j−jk)​⋅ω4ji​⋅si⋅(ni​)=k=0∑3​41​ak​j=0∑3​ω4(4j−jk)​i=0∑n​ωji⋅si⋅(ni​)=k=0∑3​41​ak​j=0∑3​ω4(4j−jk)​(s⋅ω4j​+1)n​
拿出来，再写一遍
$\begin{array}{c}{\displaystyle ans=\sum _{i=0}^3\frac{1}{4}{a}_i\sum _{j=0}^3{\omega }_4^{(4j-ij)}{(s\cdot {\omega }_4^j+1)}^n}\end{array}$ans=i=0∑3​41​ai​j=0∑3​ω4(4j−ij)​(s⋅ω4j​+1)n​

$Code$Code

#include <cstdio>
#define ll long long
using namespace std;
const int mod = 998244353;
const int w [] = {1,911660635,998244352,86583718};
ll T,n,s,ans,res,inv;
ll a[4];
ll ksm (ll a,ll b)
{
	a%=mod;
	ll s=1;
	for (;b;b>>=1,a=a*a%mod)
		if (b&1)	s=s*a%mod;
	return s;
}
int main ()
{
	scanf("%lld",&T);
	inv=ksm(4,mod-2);
	while (T--){
		scanf("%lld%lld%lld%lld%lld%lld",&n,&s,&a[0],&a[1],&a[2],&a[3]);
		ans=0;
		for (int i=0;i<=3;++i){
			res=0;
			for (int j=0;j<=3;++j)
				res=(res+w[(4*j-i*j)%4]*ksm(s*w[j]+1,n)%mod)%mod;
			ans=(ans+a[i]*res%mod)%mod;
		}
		printf("%lld\n",ans*inv%mod);
	}
	return 0;
}

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧