机械制造网站,学校网站登录入口,提升学历被骗怎么投诉,游戏小程序代理Loj#6485. LJJ 学二项式定理#xff08;单位根反演#xff09;
题目描述
题目描述 题意#xff1a;求下面式子的答案QAQ。 [∑((ni)⋅si⋅aimod4)]mod998244353[\sum(\tbinom{n}{i}\cdot s^i \cdot a_{i\;\;mod\;\;4}) ]\;mod\;\;998244353 [∑((in)⋅si⋅aimod4)]mod…Loj#6485. LJJ 学二项式定理单位根反演
题目描述
题目描述 题意求下面式子的答案QAQ。 [∑((ni)⋅si⋅aimod4)]mod998244353[\sum(\tbinom{n}{i}\cdot s^i \cdot a_{i\;\;mod\;\;4}) ]\;mod\;\;998244353 [∑((in)⋅si⋅aimod4)]mod998244353
Solution
The first 单位根反演题 of me。 题目中的式子很有趣它的形式为∑aimod4\sum a_{i \;\;mod \;\;4}∑aimod4 这就是一个典型的单位根反演的形式因此考虑单位根反演的公式 1n∑i0n−1ωik[n∣k]\frac{1}{n}\sum_{i0}^{n-1} \omega^{ik}[n|k] n1i0∑n−1ωik[n∣k] 我们枚举ki%4ki\%4ki%4原式变为 ∑k03ak∑i0n[4∣i4−k]si⋅(ni)\sum_{k0}^3 a_k \sum_{i0}^n [4|i4-k]s^i \cdot \tbinom{n}{i} k0∑3aki0∑n[4∣i4−k]si⋅(in) 单位根反演替换[4∣i4−k][4|i4-k][4∣i4−k]进一步化简得到 ∑k03ak∑i0n∑j03ω4j(i4−k)si⋅(ni)\sum_{k0}^3 a_k \sum_{i0}^n \sum_{j0}^3 \omega_4^{j(i4-k)}s^i \cdot \tbinom{n}{i} k0∑3aki0∑nj0∑3ω4j(i4−k)si⋅(in) 整理式子 ∑k03ak∑j03ω4j(4−k)(∑i0nω4ijsi⋅(ni))\sum_{k0}^3 a_k \sum_{j0}^3 \omega_4^{j(4-k)} (\sum_{i0}^n\omega_4^{ij}s^i \cdot \tbinom{n}{i}) k0∑3akj0∑3ω4j(4−k)(i0∑nω4ijsi⋅(in)) 二项式定理一波走 ∑k03ak∑j03ω4j(4−k)(sωj1)n\sum_{k0}^3 a_k \sum_{j0}^3 \omega_4^{j(4-k)}(s\omega^j1)^n k0∑3akj0∑3ω4j(4−k)(sωj1)n 所以我们只需要预处理之后计算即可。 单次复杂度O(clgn)O(clgn)O(clgn)ccc为常数。 注意longlonglong\;\;longlonglong下面的代码defineintlldefine\;\;int\;\;lldefineintll了。
#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 llusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
inline int quick_pow(int x,int y)
{if (y0) return 1;int qquick_pow(x,y1);return (y1)?1ll*q*q%mods*x%mods:1ll*q*q%mods;
}
int a[4],w[4],P[4];
signed main() {int Caseread();int wnquick_pow(3,(mods-1)/4);int inv4quick_pow(4,mods-2);w[0]1; for (int i1;i4;i) w[i]1ll*w[i-1]*wn%mods;while (Case--) {ll nread(),sread(),ans0;for (int i0;i4;i) a[i]read();for (int i0;i4;i) P[i]quick_pow((1ll*w[i]*s1)%mods,n);for (int i0;i4;i) {int p1ll*a[i]*inv4%mods;for (int j0;j4;j) ans(ans1ll*p*w[j*(4-i)%4]%mods*P[j]%mods)%mods;}printf(%d\n,ans);}return 0;
}
