【洛谷P4705】玩游戏【二项式定理】【NTT卷积】【生成函数】【分治NTT】【函数求导】【多项式对数】
傳送門
題意:給定長度為N,MN,MN,M的序列a,ba,ba,b和ttt,隨機選取x∈[1,N],y∈[1,M]x \in[1,N],y\in[1,M]x∈[1,N],y∈[1,M],對于i=1,2,...,t,i =1,2,...,t,i=1,2,...,t,求(ax+by)i(a_x+b_y)^i(ax?+by?)i的期望
N,M,t≤100000N,M,t \leq100000N,M,t≤100000
我為什么要打這么多標簽
f(k)=∑x=1n∑y=1m(ax+by)kf(k)=\sum_{x=1}^n\sum_{y=1}^m(a_x+b_y)^kf(k)=x=1∑n?y=1∑m?(ax?+by?)k
暴力拆開
f(k)=∑x=1n∑y=1m∑i=0k(ki)axibyk?if(k)=\sum_{x=1}^n\sum_{y=1}^m\sum_{i=0}^k\binom{k}{i}a_x^ib_y^{k-i}f(k)=x=1∑n?y=1∑m?i=0∑k?(ik?)axi?byk?i?
繼續拆
f(k)=∑x=1n∑y=1m∑i=0kk!i!(k?i)!axibyk?if(k)=\sum_{x=1}^n\sum_{y=1}^m\sum_{i=0}^k\frac{k!}{i!(k-i)!}a_x^ib_y^{k-i}f(k)=x=1∑n?y=1∑m?i=0∑k?i!(k?i)!k!?axi?byk?i?
整理一下
f(k)k!=∑i=0k∑x=1naxii!∑y=1mbyk?i(k?i)!\frac{f(k)}{k!}=\sum_{i=0}^k\frac{\sum_{x=1}^na_x^i}{i!}\frac{\sum_{y=1}^mb_y^{k-i}}{(k-i)!}k!f(k)?=i=0∑k?i!∑x=1n?axi??(k?i)!∑y=1m?byk?i??
顯然是個卷積
#undef f
現在只需要求出
f(k)=∑i=1naikf(k)=\sum_{i=1}^na_i^kf(k)=i=1∑n?aik?
右邊同理
接下來是個一周目沒法想到的神仙做法
對每個數單獨考慮
fi(k)=aikf_i(k)=a_i^kfi?(k)=aik?
構造生成函數
fi(x)=1+aix+ai2x2+...f_i(x)=1+a_ix+a_i^2x^2+...fi?(x)=1+ai?x+ai2?x2+...
寫成封閉形式
fi(x)=11?aixf_i(x)=\frac{1}{1-a_ix}fi?(x)=1?ai?x1?
原來是
f(x)=∑i=1n11?aixf(x)=\sum_{i=1}^n\frac{1}{1-a_ix}f(x)=i=1∑n?1?ai?x1?
加法并不好求其實很好求,分治暴力通分就可以了
考慮轉成乘法做分治NTT
自然地想到算lnlnln
而這個式子和lnlnln有關的就只有倒數了
強行解釋
即
ln′(1?aix)=11?aixln'(1-a_ix)=\frac{1}{1-a_ix}ln′(1?ai?x)=1?ai?x1?
(上述式子的自變量是1?aix1-a_ix1?ai?x)
而
[ln(1?aix)]′=ln′(1?aix)(1?aix)′=?ai1?aix[ln(1-a_ix)]'=ln'(1-a_ix)(1-a_ix)'=-\frac{a_i}{1-a_ix}[ln(1?ai?x)]′=ln′(1?ai?x)(1?ai?x)′=?1?ai?xai??
我們發現這玩意和fff有關系
設
gi(x)=?ai1?aixg(x)=∑i=1ngi(x)g_i(x)=-\frac{a_i}{1-a_ix}\\g(x)=\sum_{i=1}^ng_i(x)gi?(x)=?1?ai?xai??g(x)=i=1∑n?gi?(x)
有
fi(x)=1?xgi(x)f_i(x)=1-xg_i(x)fi?(x)=1?xgi?(x)
所以
f(x)=n?xg(x)f(x)=n-xg(x)f(x)=n?xg(x)
現在只需要求出ggg
繼續推之前的式子
g(x)=∑i=1n?ai1?aixg(x)=\sum_{i=1}^n-\frac{a_i}{1-a_ix}g(x)=i=1∑n??1?ai?xai??
=∑i=1n[ln(1?aix)]′=\sum_{i=1}^n[ln(1-a_ix)]'=i=1∑n?[ln(1?ai?x)]′
腦補一下,導數是可加的
g(x)=[∑i=1nln(1?aix)]′g(x)=[\sum_{i=1}^nln(1-a_ix)]'g(x)=[i=1∑n?ln(1?ai?x)]′
拆進去
g(x)=[ln∏i=1n(1?aix)]′g(x)=[ln\prod_{i=1}^n(1-a_ix)]'g(x)=[lni=1∏n?(1?ai?x)]′
分治NTT即可
復雜度O(nlog2n)O(nlog^2n)O(nlog2n)
#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #define MAXN 262144+5 using namespace std; const int MOD=998244353; typedef long long ll; int fac[MAXN],finv[MAXN]; inline int add(const int& x,const int& y){return x+y>=MOD? x+y-MOD:x+y;} inline int dec(const int& x,const int& y){return x<y? x-y+MOD:x-y;} inline int qpow(int a,int p) {int ans=1;while (p){if (p&1) ans=(ll)ans*a%MOD;a=(ll)a*a%MOD;p>>=1;}return ans; } #define inv(x) qpow(x,MOD-2) int r[MAXN],rt[2][MAXN]; inline void init(const int& l){for (int i=0;i<(1<<l);i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));} void NTT(int* a,int l,int type) {int lim=1<<l;for (int i=0;i<lim;i++) if (i<r[i]) swap(a[i],a[r[i]]);for (int L=0;L<l;L++){int mid=1<<L,len=mid<<1;int Wn=rt[type][L+1];for (int s=0;s<lim;s+=len)for (int k=0,w=1;k<mid;k++,w=(ll)w*Wn%MOD){int x=a[s+k],y=(ll)w*a[s+mid+k]%MOD;a[s+k]=add(x,y);a[s+mid+k]=dec(x,y);}}if (type){int t=inv(lim);for (int i=0;i<lim;i++) a[i]=(ll)a[i]*t%MOD;} } void getinv(int* A,int* B,int n) {static int t[MAXN];if (n==1) return (void)(*B=inv(*A));getinv(A,B,(n+1)>>1);int l=0;while ((1<<l)<(n<<1)) ++l;for (int i=0;i<n;i++) t[i]=A[i];for (int i=n;i<(1<<l);i++) t[i]=B[i]=0;init(l);NTT(t,l,0);NTT(B,l,0);for (int i=0;i<(1<<l);i++) B[i]=(ll)B[i]*(MOD+2-(ll)t[i]*B[i]%MOD)%MOD;NTT(B,l,1);for (int i=n;i<(1<<l);i++) B[i]=0; } inline void deriv(int* A,int* B,int n) {for (int i=0;i<n-1;i++) B[i]=(ll)A[i+1]*(i+1)%MOD;B[n-1]=0; } inline void integ(int* A,int* B,int n) {for (int i=1;i<n;i++) B[i]=(ll)A[i-1]*finv[i]%MOD*fac[i-1]%MOD;B[0]=0; } void getln(int* A,int* B,int n) {static int f[MAXN],g[MAXN];deriv(A,f,n);getinv(A,g,n);int l=0;while ((1<<l)<(n<<1)) ++l;init(l);for (int i=n;i<(1<<l);i++) f[i]=g[i]=0;NTT(f,l,0);NTT(g,l,0);for (int i=0;i<(1<<l);i++) f[i]=(ll)f[i]*g[i]%MOD;NTT(f,l,1);integ(f,B,n); } void solve(int* a,int* f,int l,int r) {if (l==r){f[0]=1;f[1]=MOD-a[l];return;}int mid=(l+r)>>1;int len=0;while ((1<<len)<=r-l+1) ++len;int L[(1<<len)+5],R[(1<<len)+5];memset(L,0,sizeof(L));memset(R,0,sizeof(R));solve(a,L,l,mid);solve(a,R,mid+1,r);init(len);NTT(L,len,0);NTT(R,len,0);for (int i=0;i<(1<<len);i++) f[i]=(ll)L[i]*R[i]%MOD;NTT(f,len,1); } int a[MAXN],b[MAXN]; int f[MAXN],g[MAXN]; int A[MAXN],B[MAXN]; int main() {rt[0][23]=qpow(3,119);rt[1][23]=inv(rt[0][23]);for (int i=22;i>=0;i--){rt[0][i]=(ll)rt[0][i+1]*rt[0][i+1]%MOD;rt[1][i]=(ll)rt[1][i+1]*rt[1][i+1]%MOD;}int n,m;scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&a[i]);for (int i=1;i<=m;i++) scanf("%d",&b[i]);int t;scanf("%d",&t);fac[0]=1;for (int i=1;i<=t;i++) fac[i]=(ll)fac[i-1]*i%MOD;finv[t]=inv(fac[t]);for (int i=t-1;i>=0;i--) finv[i]=(ll)finv[i+1]*(i+1)%MOD;solve(a,g,1,n);getln(g,f,t+1);deriv(f,g,t+1);for (int i=1;i<=t;i++) A[i]=MOD-g[i-1];A[0]=n;memset(f,0,sizeof(f));memset(g,0,sizeof(g));solve(b,g,1,m);getln(g,f,t+1);deriv(f,g,t+1);for (int i=1;i<=t;i++) B[i]=MOD-g[i-1];B[0]=m; // for (int i=0;i<=t;i++) printf("%d%c",A[i]," \n"[i==t]); // for (int i=0;i<=t;i++) // { // int sum=0; // for (int k=1;k<=n;k++) sum=add(sum,qpow(a[k],i)); // printf("%d%c",sum," \n"[i==t]); // } // for (int i=0;i<=t;i++) printf("%d%c",B[i]," \n"[i==t]); // for (int i=0;i<=t;i++) // { // int sum=0; // for (int k=1;k<=m;k++) sum=add(sum,qpow(b[k],i)); // printf("%d%c",sum," \n"[i==t]); // } for (int i=0;i<=t;i++){A[i]=(ll)A[i]*finv[i]%MOD;B[i]=(ll)B[i]*finv[i]%MOD;}int l=0;while ((1<<l)<=(t<<1)) ++l;init(l);NTT(A,l,0);NTT(B,l,0);for (int i=0;i<(1<<l);i++) A[i]=(ll)A[i]*B[i]%MOD;NTT(A,l,1);for (int i=1;i<=t;i++) A[i]=(ll)A[i]*fac[i]%MOD;int tmp=(ll)inv(n)*inv(m)%MOD;for (int i=1;i<=t;i++) printf("%d\n",(ll)A[i]*tmp%MOD);return 0; }總結
以上是生活随笔為你收集整理的【洛谷P4705】玩游戏【二项式定理】【NTT卷积】【生成函数】【分治NTT】【函数求导】【多项式对数】的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 耳石症耳内仍有胀气是怎么回事?
- 下一篇: 【CF700E】Cool Slogans