【LOJ#6485】LJJ 学二项式定理（单位根反演）

题面

题解

显然对于\(a0,a1,a2,a3\)分开算答案。

这里以\(a0\)为例

\[\begin{aligned}
Ans&=\frac{1}{4}a_0\sum_{i=0}^n [4|i]{n\choose i}s^i\\
&=\frac{1}{4}a_0\sum_{i=0}^n{n\choose i}s^i\sum_{j=0}^3 (\omega_4^{j})^i\\
&=\frac{1}{4}a_0\sum_{j=0}^3\sum_{i=0}^n {n\choose i}s^i(\omega_4^j)^i\\
&=\frac{1}{4}a_0\sum_{j=0}^3(s\omega_4^j+1)^n
\end{aligned}\]

另外几个只需要把\([4|i]\)变成\([4|(i+k)]\)的形式，然后在计算的时候把\(\omega_4^k\)给提取出来就行了。

#include<iostream>

#include<cstdio>

using namespace std;

#define ll long long

#define MOD 998244353

inline ll read()

{

	ll x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int fpow(int a,ll b){int s=1;while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}return s;}

int s,a[4],w,ans;ll n;

int main()

{

	int T=read();w=fpow(3,(MOD-1)/4);

	while(T--)

	{

		n=read();s=read();ans=0;

		for(int i=0;i<4;++i)a[i]=read();

		for(int i=0;i<4;++i)

			for(int j=0,t=s,ww=1;j<4;++j,t=1ll*t*w%MOD,ww=1ll*ww*w%MOD)

				ans=(ans+1ll*a[i]*fpow(t+1,n)%MOD*fpow(ww,4-i))%MOD;

		ans=1ll*ans*fpow(4,MOD-2)%MOD;

		printf("%d\n",ans);

	}

}

巴特西

【LOJ#6485】LJJ 学二项式定理（单位根反演）

【LOJ#6485】LJJ 学二项式定理（单位根反演）

题面

题解

最新文章

热门文章