手机上编写app,网站关键词优化实验结果分析,邯山网站制作,科技志愿信息平台链式反应
题目描述
不想看题面#xff0c;其实就是给定p(x)p(x)p(x)#xff0c;有f′(x)f(x)2p(x)1f(x)f(x)^2p(x)1f′(x)f(x)2p(x)1#xff0c;求fff这个多项式的幂级数形式前nnn项。
Solution
式子可以写成fn∑i,j[0ijn]fifjpn−i−j−1f_n\sum_{i,j}[0ij…链式反应
题目描述
不想看题面其实就是给定p(x)p(x)p(x)有f′(x)f(x)2p(x)1f(x)f(x)^2p(x)1f′(x)f(x)2p(x)1求fff这个多项式的幂级数形式前nnn项。
Solution
式子可以写成fn∑i,j[0ijn]fifjpn−i−j−1f_n\sum_{i,j}[0ijn]f_if_jp_{n-i-j-1}fn∑i,j[0ijn]fifjpn−i−j−1。
显然能分治FFTFFTFFT。 设分治区间为[l,r][l,r][l,r]考虑[l,mid][l,mid][l,mid]对[mid1,r][mid1,r][mid1,r]的贡献。 当l1l1l1时贡献为 ∑i0mid∑j0mid∑k0rfifjpk\sum^{mid}_{i0}\sum^{mid}_{j0}\sum^{r}_{k0}f_if_jp_k i0∑midj0∑midk0∑rfifjpk 当l1l1l1时有2lr2lr2lr因此贡献为 2∑ilmid∑j0r−l∑k0r−lfifjpk2\sum^{mid}_{il}\sum^{r-l}_{j0}\sum^{r-l}_{k0}f_if_jp_k 2il∑midj0∑r−lk0∑r−lfifjpk 时间复杂度两只lglglg。 注意这里的f,pf,pf,p始终是一个EGFEGFEGF。
#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 secondusing 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 g3;
const int gi(mods1)/3;
const int MAXN2000005;
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;
}
int Limit,L;
char st[MAXN];
int F[MAXN],G[MAXN],P[MAXN],H[MAXN],Q[MAXN],rev[MAXN],inv[MAXN],fac[MAXN],n;
inline int upd(int x,int y) { return (xymods)?xy-mods:xy; }
inline int quick_pow(int x,int y)
{int ret1;for (;y;y1){if (y1) ret1ll*ret*x%mods;x1ll*x*x%mods;}return ret;
}
inline void Init(int n)
{fac[0]1;for (int i1;in;i) fac[i]1ll*fac[i-1]*i%mods;inv[n]quick_pow(fac[n],mods-2);for (int in-1;i0;i--) inv[i]1ll*inv[i1]*(i1)%mods;
}
void Number_Theoretic_Transform(int *A,int opt)
{for (int i0;iLimit;i) if (irev[i]) swap(A[i],A[rev[i]]);for (int i1;iLimit;i1){int Wnquick_pow(opt1?g:gi,(mods-1)/(i1));for (int j0;jLimit;j(i1))for (int kj,w1;kji;k,w1ll*w*Wn%mods){int xA[k],y1ll*A[ki]*w%mods;A[k]upd(x,y),A[ki]upd(x,mods-y);}}if (opt-1){int invlimquick_pow(Limit,mods-2);for (int i0;iLimit;i) A[i]1ll*A[i]*invlim%mods;}
}
void solve(int l,int r)
{if (lr) { if (l1) F[l](mods1)1;else F[l]1ll*F[l]*inv[l]%mods*fac[l-1]%mods;printf(%d\n,2ll*F[l]*fac[l]%mods);return; }int mid(lr)1;solve(l,mid);if (l1){Limit1,L0;int lenmid*2r;while (Limitlen) Limit1,L;for (int i0;iLimit;i) rev[i](rev[i1]1)|((i1)(L-1));for (int i0;iLimit;i) H[i]G[i]0;for (int i0;ir;i) H[i]P[i];for (int i0;imid;i) G[i]F[i];Number_Theoretic_Transform(G,1);Number_Theoretic_Transform(H,1);for (int i0;iLimit;i) G[i]1ll*G[i]*G[i]%mods*H[i]%mods;Number_Theoretic_Transform(G,-1);for (int imid1;ir;i) F[i]upd(F[i],G[i]);}else{Limit1,L0;int len(mid-l)(r-l)*2;while (Limitlen) Limit1,L;for (int i0;iLimit;i) rev[i](rev[i1]1)|((i1)(L-1));for (int i0;iLimit;i) H[i]G[i]Q[i]0;for (int i0;ir-l;i) H[i]P[i];for (int i0;imid-l;i) G[i]F[il];for (int i0;ir-l;i) Q[i]F[i];Number_Theoretic_Transform(G,1);Number_Theoretic_Transform(Q,1);Number_Theoretic_Transform(H,1);for (int i0;iLimit;i) G[i]1ll*G[i]*Q[i]%mods*H[i]%mods;Number_Theoretic_Transform(G,-1);for (int imid1;ir;i) F[i]upd(F[i],upd(G[i-l],G[i-l]));}solve(mid1,r);
}
int main()
{nread();Init(n);scanf(%s,st);for (int i1;in;i) P[i](st[i-1]-0)*inv[i-1];solve(1,n);return 0;
}
