傳送門

題意：給定$n$和集合$S$，求含$n$個葉子結(jié)點、非葉子節(jié)點的兒子數(shù)在$S$內(nèi)的樹的個數(shù) 模 $950009857(453\times 2^{21}+1)$。結(jié)點無標(biāo)號但兒子間有順序。

$n\le 10^5$

算是拉格朗日反演模版題了吧……

先是拉格朗日反演

對于兩個不含常數(shù)項，且一次項非$0$的多項式$F(x),G(x)$,如果$F(G(x))=x$（當(dāng)然要取模），稱$F$是$G$的復(fù)合逆。

人話：反函數(shù)

根據(jù)高中數(shù)學(xué)知識，$F(x)$和$G(x)$互為反函數(shù)，所以$G(F(x))=x$也成立

所以下面的$F$和$G$可以互換

現(xiàn)在考慮$G(F(x))=x$,如果知道$G(x)$如何求$F(x)$的$n$次項系數(shù)

設(shè)
$$G(x)=\sum _{i=1}^{\infty }{a}_i{x}^i$$

代入$F(x)$

$$\sum _{i=0}^{\infty }{a}_i{F}^i(x)=x$$

閑著沒事求個導(dǎo)

$$\sum _{i=0}^{\infty }i{a}_i{F}^{i?1}(x)F^{\prime }(x)=1$$

同時除以$F^n(x)$

$$\sum _{i=0}^{\infty }i{a}_i{F}^{i?n?1}(x)F^{\prime }(x)=\frac{1}{F^n(x)}$$

同時取$?1$次項

$$[x^{?1}]\sum _{i=0}^{\infty }i{a}_i{F}^{i?n?1}(x)F^{\prime }(x)=[x^{?1}]\frac{1}{F^n(x)}$$

什么？為什么有負(fù)數(shù)項？

這個涉及到一些抽象代數(shù)的知識，這里肯定講不了了

不過可以簡單粗暴的理解成：

兩個多項式相除$F(x)/G(x)$,發(fā)現(xiàn)$G(x)$沒有常數(shù)項無法求逆，于是把$G(x)$寫成$G_0(x)x^n$，其中$G_0(x)$有常數(shù)項。

這樣$G_0(x)$就有逆了，算出來之后平移$n$位就有了負(fù)下標(biāo)，形如

$$...a_{?2}{x}^{?2}+a_{?1}{x}^{?1}+a_0+a_{1}x+...$$

只需要知道：這個負(fù)下標(biāo)是為了解決沒有逆的情況，和多項式求逆不矛盾

好繼續(xù)

$$[x^{?1}]\sum _{i=0}^{\infty }i{a}_i{F}^{i?n?1}(x)F^{\prime }(x)=[x^{?1}]\frac{1}{F^n(x)}$$

中間那團(tuán)看著不爽，提出來研究一下

$$F^{i?n?1}(x)F^{\prime }(x)$$

它等于

$$\frac{(F^{i?n}{)}^{\prime }(x)}{i?n}$$

當(dāng)$i=n$的時候沒有意義，考慮$i=n$

發(fā)現(xiàn)這個情況下$F^{i?n}$是個多項式……

什么？為什么？

首先$i>n$肯定沒問題

$i<n$的時候相當(dāng)于求個逆再求冪，它就（yi）算（ding）沒有逆，我們也有負(fù)下標(biāo)可以用來平移

這樣允許負(fù)次冪的多項式求導(dǎo)之后一定沒有$?1$次項，因為求導(dǎo)相當(dāng)于集體左移一位，而$0$次項并不能移到$?1$次項……

（并不知道對不對，感性理解好了）

所以我們只需要考慮$i=n$的情況

也就是

$$F^{?1}(x)F^{\prime }(x)$$

設(shè)

$$F(x)=\sum _{i=1}^{\infty }{b}_i{x}^i$$

那么上面的式子可以寫成

$$\frac{b_1+2b_{2}x+3b_3{x}^2+4b_4{x}^3+...}{b_{1}x+b_2{x}^2+b_3{x}^3+b_4{x}^4+...}$$

把下面強行拆開

$$\frac{b_1+2b_{2}x+3b_3{x}^2+4b_4{x}^3+...}{b_{1}x}\frac{1}{1+\frac{b_2}{b_1}x+\frac{b_3}{b_1}{x}^2+\frac{b_4}{b_1}{x}^3+...}$$

注意到右邊是一個正宗的多項式，并且常數(shù)項為$1$,存在逆元；而左邊的$\frac{b_1}{b_{1}x}$會貢獻(xiàn)出一個$x^{?1}$

所以這一團(tuán)的$?1$次項為$1$

代回原式

$$n{a}_n=[x^{?1}]\frac{1}{F^n(x)}$$

$$[x^n]G(x)=\frac{1}{n}[x^{?1}]\frac{1}{F^n(x)}$$

沒了……

哎等等，道理我都懂，可是負(fù)次冪怎么求呢？

那就右邊平移吧

$$[x^n]G(x)=\frac{1}{n}[x^{n?1}][\frac{x}{F(x)}{]}^n$$

這樣$F(x)$剛好可以約一個$x$,就可以求逆啦

---

然后這道題就很容易了

設(shè)$f(n)$表示$n$個葉子時的答案，有$f(1)=1$

然后構(gòu)造生成函數(shù)$F(x)$

可以得到

$$F(x)=\sum _{d\in S}{F}^d(x)+x$$

移個項

$$F(x)?\sum _{d\in S}{F}^d(x)=x$$

設(shè)

$$G(x)=x?\sum _{d\in S}{x}^d$$

有

$$G(F(x))=x$$

套結(jié)論即可

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #define MAXN 400005 using namespace std; inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } const int MOD=950009857; typedef long long ll; 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 rt[2][22]; int l,r[MAXN]; inline void init(){for (int i=0;i<(1<<l);i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));} inline void NTT(int* a,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,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)a[s+mid+k]*w%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 f[MAXN],t[MAXN];if (n==1) return (void)(*B=inv(*A));getinv(A,t,(n+1)>>1);l=0;while ((1<<l)<(n<<1)) ++l;init();for (int i=0;i<n;i++) f[i]=A[i];for (int i=n;i<(1<<l);i++) f[i]=t[i]=0;NTT(f,0);NTT(t,0);for (int i=0;i<(1<<l);i++) B[i]=(ll)t[i]*dec(2,(ll)f[i]*t[i]%MOD)%MOD;NTT(B,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]*inv(i)%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);for (int i=n;i<(1<<l);i++) f[i]=g[i]=0;NTT(f,0);NTT(g,0);for (int i=0;i<(1<<l);i++) f[i]=(ll)f[i]*g[i]%MOD;NTT(f,1);integ(f,B,n);for (int i=n;i<(1<<l);i++) B[i]=0; } void getexp(int* A,int* B,int n) {static int f[MAXN],g[MAXN];if (n==1) return (void)(*B=1);getexp(A,g,(n+1)>>1);getln(g,f,n);for (int i=0;i<n;i++) f[i]=dec(A[i],f[i]);++f[0];for (int i=n;i<(1<<l);i++) f[i]=g[i]=0;NTT(f,0);NTT(g,0);for (int i=0;i<(1<<l);i++) B[i]=(ll)f[i]*g[i]%MOD;NTT(B,1);for (int i=n;i<(1<<l);i++) B[i]=0; } int a[MAXN],t[MAXN]; int main() {rt[0][21]=qpow(5,453);rt[1][21]=inv(rt[0][21]);for (int i=20;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,k;n=read(),k=read();a[0]=1;while (k--) a[read()-1]=MOD-1;getinv(a,t,n);getln(t,a,n);for (int i=0;i<n;i++) a[i]=(ll)a[i]*n%MOD;getexp(a,t,n);int ans=(ll)t[n-1]*inv(n)%MOD;printf("%d\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【BZOJ3684】大朋友和多叉树【生成函数】【拉格朗日反演】【多项式幂函数】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。