【loj6485】LJJ學二項式定理【機關根反演】【二項式】

傳送門

也是闆子。求

對于這個下标取模，我們直接拆成四個式子，形如

直接機關根反演後面這一坨

然後就可以做了，最後那一個跟着走就行。

把k取遍0123加起來。記得除以4。

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define int long long
int in{
	int cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){
		ch=getchar();if(ch=='-')f=-1;
	}
	while(isdigit(ch)){
		cnt=cnt*10+ch-48;
		ch=getchar(); 
	}return cnt*f;
}
const int mod=998244353;
int n,s,a[5];
int w;int ans;
int ksm(int a,int b){
	int sum=1;a%=mod;
	while(b){
		if(b&1)sum=sum*a%mod;a=a*a%mod;b>>=1;
	}return sum;
}
signed main(){
	int t=in;w=ksm(3,(mod-1)/4);
	while(t--){
		n=in;s=in;for(int i=0;i<4;i++)a[i]=in;
		ans=0;
		for(int i=0;i<4;i++){
			for(int j=0,ww=1;j<4;j++,ww=ww*w%mod)
			ans=(ans+a[i]*ksm(s*ww%mod+1,n)%mod*ksm(ww,4-i)%mod)%mod;
		}
		cout<<ans*ksm(4,mod-2)%mod<<'\n';
	}
	return 0;
}