塔里木油田公司档案馆网站建设研究,企业网站开发研究现状,做网站成品,wordpress评价功能传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; 思路#xff1a;
写一下式子#xff0c;发现每个fif_ifi只有左边的fff对他有影响#xff0c;所以考虑分治FFTFFTFFT来解决这个问题。 先递归左边#xff0c;让后计算对右边贡献#xff0c;再递归右边…传送门
文章目录题意思路题意 思路
写一下式子发现每个fif_ifi只有左边的fff对他有影响所以考虑分治FFTFFTFFT来解决这个问题。 先递归左边让后计算对右边贡献再递归右边。 式子化简一下就是fi∑jlmidfj∗gi−jf_i\sum_{jl}^{mid}f_j*g_{i-j}fi∑jlmidfj∗gi−j直接写就好注意卡常。。如果偷懒直接长度为nnn的乘起来会TTT很多点所以需要偏移一下。
// Problem: P3803 【模板】多项式乘法FFT
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3803
// Memory Limit: 500 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N4000010,mod998244353,INF0x3f3f3f3f;
const double eps1e-6;int n;
LL g[N],f[N];
LL a[N], b[N];
struct NTT {int P 998244353, G 3, Gi 332748118;int n, m, limit 1, L, r[N];LL qmi[2][N];inline LL fastpow(LL a, LL k) {LL base 1;while(k) {if(k 1) base (base * a ) % P;a (a * a) % P;k 1;}return base % P;}inline void ntt(LL *A, int type) {for(int i 0; i limit; i) if(i r[i]) swap(A[i], A[r[i]]);for(int mid 1; mid limit; mid 1) { LL Wnqmi[type1? 1:0][mid];// LL t fastpow( type 1 ? G : Gi , (P - 1) / (mid 1));for(int j 0; j limit; j (mid 1)) {LL w 1;for(int k 0; k mid; k, w (w * Wn) % P) {int x A[j k], y w * A[j k mid] % P;A[j k] (x y) % P,A[j k mid] (x - y P) % P;}}}}void init_qmi() {for(int mid1;mid4e5;mid1) {qmi[1][mid]fastpow(G,(P - 1) / (mid 1));qmi[0][mid]fastpow(Gi,(P - 1) / (mid 1));}}void init(int n,int m) {limit1; L0;while(limit m n) limit 1, L;for(int i 0; i limit; i) r[i] (r[i 1] 1) | ((i 1) (L - 1));}int mul(LL *ans,LL *x,int ln,int rn,LL *y,int rm) {for(int iln;irn;i) a[i-ln]x[i]%P;for(int i1;irm;i) b[i]y[i]%P; int nrn-ln1,mrm;init(rn,rm);ntt(a, 1); ntt(b, 1); ntt(a, -1); LL inv fastpow(limit, P - 2);for(int i 0; i ln rm; i) ans[i]a[i]*inv%P;for(int i0;ilimit;i) a[i]0,b[i]0;return rnrm;}}NT;void solve(int l,int r) {if(lr) {if(l0) f[l]1;return;} int mid(lr)1;solve(l,mid);int lenr-l1;for(int il;imid;i) a[i-l]f[i];for(int i0;ilen;i) b[i]g[i];NT.init(len1,len); NT.ntt(a, 1); NT.ntt(b, 1); for(int i 0; i NT.limit; i) a[i] (a[i] * b[i]) % NT.P;NT.ntt(a, -1); LL inv NT.fastpow(NT.limit, NT.P - 2);for(int i mid1; i r; i) f[i]a[i-l]*inv%NT.P,f[i]%mod;for(int i0;iNT.limit;i) a[i]0,b[i]0;solve(mid1,r);
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d,n);for(int i1;in-1;i) scanf(%lld,g[i]);NT.init_qmi();solve(0,n-1);for(int i0;in;i) printf(%lld ,f[i]);return 0;
}
/**/
