网站seo快速优化技巧,网站策划,建设项目环境登记表辽宁省网站,萍乡建网站题意#xff1a;有一个整数x∈[0,n]x\in[0,n]x∈[0,n]#xff0c;取iii的概率为pip_ipi。执行mmm次操作#xff0c;每次把xxx等概率变成[0,x][0,x][0,x]中的一个整数#xff0c;求操作完后等于每个数的概率。模998244353998244353998244353。 n≤105,m≤1018n\leq 10^5,m…题意有一个整数x∈[0,n]x\in[0,n]x∈[0,n]取iii的概率为pip_ipi。执行mmm次操作每次把xxx等概率变成[0,x][0,x][0,x]中的一个整数求操作完后等于每个数的概率。模998244353998244353998244353。
n≤105,m≤1018n\leq 10^5,m\leq10^{18}n≤105,m≤1018
显然有一个dp式子
fi,j∑kjnfi−1,kk1f_{i,j}\sum_{kj}^n\frac{f_{i-1,k}}{k1}fi,jkj∑nk1fi−1,k
考虑生成函数
fi(x)∑j0n∑kjn[xk]fi−1(x)k1xjf_i(x)\sum_{j0}^n\sum_{kj}^n\frac{[x^k]f_{i-1}(x)}{k1}x^jfi(x)j0∑nkj∑nk1[xk]fi−1(x)xj
∑k0n[xk]fi−1(x)k1∑j0kxj\sum_{k0}^n\frac{[x^k]f_{i-1}(x)}{k1}\sum_{j0}^kx^jk0∑nk1[xk]fi−1(x)j0∑kxj
等比数列求和
∑k0n[xk]fi−1(x)k1xk1−1x−1\sum_{k0}^n\frac{[x^k]f_{i-1}(x)}{k1}\frac{x^{k1}-1}{x-1}k0∑nk1[xk]fi−1(x)x−1xk1−1
似乎推不动了
但是有奥妙重重的一步
∑k0n[xk]fi−1(x)x−1xk1−1k1\sum_{k0}^n\frac{[x^k]f_{i-1}(x)}{x-1}\frac{x^{k1}-1}{k1}k0∑nx−1[xk]fi−1(x)k1xk1−1
看起来没啥用但这样把右边写成了积分的形式
∑k0n[xk]fi−1(x)x−1∫1xtkdt\sum_{k0}^n\frac{[x^k]f_{i-1}(x)}{x-1}\int_1^xt^kdtk0∑nx−1[xk]fi−1(x)∫1xtkdt
然后盯着这个式子
∑k0n[xk]fi−1(x)∫1xtkdt\sum_{k0}^n[x^k]f_{i-1}(x)\int_1^xt^kdtk0∑n[xk]fi−1(x)∫1xtkdt
ttt可能看不习惯换个更通用的写法
∑k0n[xk]f(x)∫LRxkdx\sum_{k0}^n[x^k]f(x) \int_L^Rx^kdxk0∑n[xk]f(x)∫LRxkdx
相当于把多项式拆成单项式每个单项式对区间[L,R][L,R][L,R]求定积分最后还贴心地帮你乘上了系数
那不就是对多项式求积分吗
∫LRf(x)dx\int_L^Rf(x)dx∫LRf(x)dx
代回原式
fi(x)1x−1∫1xfi−1(t)dtf_i(x)\frac{1}{x-1}\int_1^xf_{i-1}(t)dtfi(x)x−11∫1xfi−1(t)dt
然而这个积分下界是111不好处理
然后又是奥妙重重的一步
令gi(x)fi(x1)g_i(x)f_i(x1)gi(x)fi(x1)
gi(x)1x∫1x1fi−1(t)dtg_i(x)\frac{1}{x}\int_1^{x1}f_{i-1}(t)dtgi(x)x1∫1x1fi−1(t)dt
1x∫0xfi−1(t1)dt\frac{1}{x}\int_0^{x}f_{i-1}(t1)dtx1∫0xfi−1(t1)dt
1x∫0xgi−1(t)dt\frac{1}{x}\int_0^{x}g_{i-1}(t)dtx1∫0xgi−1(t)dt
那就gi−1g_{i-1}gi−1的不定积分在xxx处的取值容易得出
gi,j1j1gi−1,jg_{i,j}\frac{1}{j1}g_{i-1,j}gi,jj11gi−1,j
这样如果知道g0g_0g0就可以轻松算出gmg_mgm
而fff和ggg直接二项式定理暴拆再卷积一下就可以互相转换问题解决
复杂度O(nlogn)O(n\log n)O(nlogn)
#include iostream
#include cstdio
#include cstring
#include cctype
#define MAXN 262144
using namespace std;
const int MOD998244353;
typedef long long ll;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
inline int qpow(int a,int p)
{int ans1;while (p){if (p1) ans(ll)ans*a%MOD;a(ll)a*a%MOD;p1;}return ans;
}
#define inv(x) qpow(x,MOD-2)
inline int add(const int x,const int y){return xyMOD? xy-MOD:xy;}
inline int dec(const int x,const int y){return xy? x-yMOD:x-y;}
int rt[2][24];
int r[MAXN],l,lim;
inline void init(){lim1l;for (int i0;ilim;i) r[i](r[i1]1)|((i1)(l-1));}
inline void NTT(int* a,int type)
{for (int i0;ilim;i) if (ir[i]) swap(a[i],a[r[i]]);for (int L0;Ll;L){int mid1L,lenmid1;ll Wnrt[type][L1];for (int s0;slim;slen)for (int k0,w1;kmid;k,ww*Wn%MOD){int xa[sk],y(ll)w*a[smidk]%MOD;a[sk]add(x,y),a[smidk]dec(x,y);}}if (type){int tinv(lim);for (int i0;ilim;i) a[i](ll)a[i]*t%MOD;}
}
int fac[MAXN],finv[MAXN];
int a[MAXN];
int f[MAXN],g[MAXN];
int main()
{rt[0][23]qpow(3,119);rt[1][23]inv(rt[0][23]);for (int i22;i0;i--){rt[0][i](ll)rt[0][i1]*rt[0][i1]%MOD;rt[1][i](ll)rt[1][i1]*rt[1][i1]%MOD;}int nread();ll m;scanf(%lld,m);m%MOD-1;for (int i0;in;i) a[i]read();fac[0]1;for (int i1;in;i) fac[i](ll)fac[i-1]*i%MOD;finv[n]inv(fac[n]);for (int in-1;i0;i--) finv[i](ll)finv[i1]*(i1)%MOD;for (int i0;in;i) f[i](ll)a[i]*fac[i]%MOD;for (int i0;in;i) g[i]finv[n-i];for (l0;(1l)(n1);l);init();NTT(f,0);NTT(g,0);for (int i0;ilim;i) f[i](ll)f[i]*g[i]%MOD;NTT(f,1);for (int i0;in;i) a[i](ll)f[in]*finv[i]%MOD;for (int i0;in;i) a[i](ll)a[i]*inv(qpow(i1,m))%MOD;for (int i0;in;i) f[i](ll)a[i]*fac[i]%MOD;for (int i0;in;i) g[i](((n-i)1)? MOD-finv[n-i]:finv[n-i]);for (int in1;ilim;i) f[i]g[i]0;NTT(f,0);NTT(g,0);for (int i0;ilim;i) f[i](ll)f[i]*g[i]%MOD;NTT(f,1);for (int i0;in;i) a[i](ll)f[in]*finv[i]%MOD;for (int i0;in;i) printf(%d ,a[i]);return 0;
}
