Loj#6485. LJJ 學二項式定理

Loj#6485. LJJ 學二項式定理（機關根反演）

題目描述

題目描述

題意：求下面式子的答案QAQ。

[ ∑ ( ( n i ) ⋅ s i ⋅ a i      m o d      4 ) ]    m o d      998244353 [\sum(\tbinom{n}{i}\cdot s^i \cdot a_{i\;\;mod\;\;4}) ]\;mod\;\;998244353 [∑((in​)⋅si⋅aimod4​)]mod998244353

Solution

The first 機關根反演題 of me。

題目中的式子很有趣，它的形式為 ∑ a i      m o d      4 \sum a_{i \;\;mod \;\;4} ∑aimod4​

這就是一個典型的機關根反演的形式，是以考慮機關根反演的公式

1 n ∑ i = 0 n − 1 ω i k = [ n ∣ k ] \frac{1}{n}\sum_{i=0}^{n-1} \omega^{ik}=[n|k] n1​i=0∑n−1​ωik=[n∣k]

我們枚舉 k = i % 4 k=i\%4 k=i%4，原式變為：

∑ k = 0 3 a k ∑ i = 0 n [ 4 ∣ i + 4 − k ] s i ⋅ ( n i ) \sum_{k=0}^3 a_k \sum_{i=0}^n [4|i+4-k]s^i \cdot \tbinom{n}{i} k=0∑3​ak​i=0∑n​[4∣i+4−k]si⋅(in​)

機關根反演，替換 [ 4 ∣ i + 4 − k ] [4|i+4-k] [4∣i+4−k]進一步化簡得到

∑ k = 0 3 a k ∑ i = 0 n ∑ j = 0 3 ω 4 j ( i + 4 − k ) s i ⋅ ( n i ) \sum_{k=0}^3 a_k \sum_{i=0}^n \sum_{j=0}^3 \omega_4^{j(i+4-k)}s^i \cdot \tbinom{n}{i} k=0∑3​ak​i=0∑n​j=0∑3​ω4j(i+4−k)​si⋅(in​)

整理式子：

∑ k = 0 3 a k ∑ j = 0 3 ω 4 j ( 4 − k ) ( ∑ i = 0 n ω 4 i j s i ⋅ ( n i ) ) \sum_{k=0}^3 a_k \sum_{j=0}^3 \omega_4^{j(4-k)} (\sum_{i=0}^n\omega_4^{ij}s^i \cdot \tbinom{n}{i}) k=0∑3​ak​j=0∑3​ω4j(4−k)​(i=0∑n​ω4ij​si⋅(in​))

二項式定理一波走：

∑ k = 0 3 a k ∑ j = 0 3 ω 4 j ( 4 − k ) ( s ω j + 1 ) n \sum_{k=0}^3 a_k \sum_{j=0}^3 \omega_4^{j(4-k)}(s\omega^j+1)^n k=0∑3​ak​j=0∑3​ω4j(4−k)​(sωj+1)n

是以我們隻需要預處理之後計算即可。

單次複雜度 O ( c + l g n ) O(c+lgn) O(c+lgn)， c c c為常數。

注意 l o n g      l o n g long\;\;long longlong，下面的代碼 d e f i n e      i n t      l l define\;\;int\;\;ll defineintll了。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
//#include <unordered_set>
//#include <unordered_map>
//#include <bits/stdc++.h>

#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se second
#define int ll

using namespace std;

template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; }
template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }

typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod eps=1e-11;
const lod pi=acos(-1);
const int oo=1<<30;
const ll loo=1ll<<62;
const int mods=998244353;
const int MAXN=600005;
const int INF=0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{
	int f=1,x=0; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }
	while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }
	return x*f;
}
inline int quick_pow(int x,int y)
{
	if (y==0) return 1;
	int q=quick_pow(x,y>>1);
	return (y&1)?1ll*q*q%mods*x%mods:1ll*q*q%mods;
}
int a[4],w[4],P[4];
signed main() {
	int Case=read();
	int wn=quick_pow(3,(mods-1)/4);
	int inv4=quick_pow(4,mods-2);
	w[0]=1; 
	for (int i=1;i<4;i++) w[i]=1ll*w[i-1]*wn%mods;
	
	while (Case--) {
		ll n=read(),s=read(),ans=0;
		for (int i=0;i<4;i++) a[i]=read();
		for (int i=0;i<4;i++) P[i]=quick_pow((1ll*w[i]*s+1)%mods,n);
		for (int i=0;i<4;i++) {
			int p=1ll*a[i]*inv4%mods;
			for (int j=0;j<4;j++) 
				ans=(ans+1ll*p*w[j*(4-i)%4]%mods*P[j]%mods)%mods;
		}
		printf("%d\n",ans);
	}
	return 0;
}