[loj2983]数树

令$E_{1}$和$E_{2}$分别为两树的边集,默认要求其构成一棵树

$op=0$

给定$E_{1}$和$E_{2}$,此时答案即$y^{n-|E_{1}cap E_{2}|}$,使用map或排序即可,复杂度为$o(nlog n)$

$op=1$

给定$E_{1}$,此时答案即$sum_{E_{2}}y^{n-|E_{1}cap E_{2}|}$

枚举$S=E_{1}cap E_{2}$,即$sum_{Ssubseteq E_{1}}y^{n-|S|}sum_{Ssubseteq E_{2}}[E_{1}cap E_{2}=S]$

对于最后一项,有$[E_{1}cap E_{2}=S]=sum_{Ssubseteq Tsubseteq E_{1}cap E_{2}}(-1)^{|T|-|S|}$

交换枚举顺序,即$sum_{Tsubseteq E_{1}}sum_{Ssubseteq T}(-1)^{|T|-|S|}y^{n-|S|}sum_{Tsubseteq E_{2}}1$

令最后一项为$f(T)$,即$sum_{Tsubseteq E_{1}}f(T)sum_{Ssubseteq T}(-1)^{|T|-|S|}y^{n-|S|}$

枚举$i=|S|$,对应方案数即${|T|choose i}$,即$sum_{Tsubseteq E_{1}}f(T)sum_{i=0}^{|T|}{|T|choose i}(-1)^{|T|-i}y^{n-i}$

提取$y^{n}$,即$y^{n}sum_{Tsubseteq E_{1}}f(T)sum_{i=0}^{|T|}{|T|choose i}(-1)^{|T|-i}(frac{1}{y})^{i}$

后者即一个二项式展开的结果,即$y^{n}sum_{Tsubseteq E_{1}}f(T)(frac{1}{y}-1)^{|T|}$

记$z=frac{1}{y}-1$,即$y^{n}sum_{Tsubseteq E_{1}}z^{|T|}f(T)$

(下面的部分可以参考cf917D,比较省略了)

假设$T$中的边将原图划分为$m$个连通块,第$i$个连通块点数为$x_{i}$,此时有$f(T)=n^{m-2}prod_{i=1}^{m}x_{i}$

将之代入并调整,即$frac{(yz)^{n}}{n^{2}}sum_{Tsubseteq E_{1}}(frac{n}{z})^{m}prod_{i=1}^{m}a_{i}$(有$m=n-|T|$)​

令$dp_{i,0/1}$表示以$i$为根的子树内,与$i$相连的连通块是否已经选择对应的点,所有方案的贡献和(每一组方案的贡献为$(frac{n}{z})^{m}$,其中$m$为已经确定全部在$i$子树内的连通块数),树形dp即可,复杂度为$o(n)$

(注意最后$dp_{rt,1}$并没有算根节点所在连通块的$frac{n}{z}$,即还要再乘上一次)

(特判$z=0$时,此时答案显然为$y^{n}f(empty)=n^{n-2}$)

$op=2$

联系$op=1$的情况,此时答案即$y^{n}sum_{E_{1}}sum_{Tsubseteq E_{1}}z^{|T|}f(T)$

交换枚举顺序,可以发现$E_{1}$的方案数也为$f(T)$,即$y^{n}sum_{T}z^{|T|}f^{2}(T)$

代入$f(T)$对应的式子并调整,即$frac{(yz)^{n}}{n^{4}}sum_{T}(frac{n^2}{z})^{m}prod_{i=1}^{m}x^{2}_{i}$

令$f_{i}=sum_{T}(frac{n^{2}}{z})^{m}prod_{j=1}^{m}x_{j}^{2}$,枚举第$i$个点连通块的大小,即有转移$f_{i}=sum_{j=1}^{i}frac{n^{2}}{z}{i-1choose j-1}j^{j}f_{i-j}$

(初始状态为$f_{0}=1$,最终即求$frac{(yz)^{n}}{n^{4}}f_{n}$)

展开组合数并调整,即有$frac{f_{i}}{(i-1)!}=sum_{j=1}^{i}frac{n^{2}j^{j}}{z(j-1)!}cdot frac{f_{i-j}}{(i-j)!}$

令$G(x)=sum_{i=1}^{infty}frac{n^{2}i^{i}}{z(i-1)!}x^{i}$,$F(x)=sum_{i=0}^{infty}frac{f_{i}}{i!}x^{i}$,即有
$$
F(x)G(x)=sum_{i=1}^{infty}(sum_{j=1}^{i}frac{n^{2}j^{j}}{z(j-1)!}frac{f_{i-j}}{(i-j)!})x^{i}=sum_{i=1}^{infty}frac{f_{i}}{(i-1)!}x^{i}
$$
考虑对$F(x)$求导,即$F'(x)=sum_{i=1}^{infty}frac{f_{i}}{(i-1)!}x^{i-1}$,即$F(x)G(x)=xF'(x)$

化简后,即$frac{G(x)}{x}=frac{F'(x)}{F(x)}=(ln F(x))'$(后者考虑$ln$的推导过程)

换言之,即$F(x)=e^{int frac{G(x)}{x}{ m d} x}=e^{sum_{i=1}^{infty}frac{n^{2}i^{i}}{zi!}x^{i}}$,多项式exp即可,复杂度为$o(nlog n)$

(特判$z=0$时,此时答案显然为$y^{n}f^{2}(empty)=n^{2(n-2)}$)

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define N 100005
  4 #define mod 998244353
  5 struct Edge{
  6     int nex,to;
  7 }edge[N<<1];
  8 struct poly{
  9     vector<int>a;
 10     poly(){
 11         a.clear();
 12     }
 13 }a;
 14 map<int,int>mat[N];
 15 int E,n,m,T,x,y,C1,C2,C3,head[N],f[N][2],fac[N],inv[N<<1];
 16 int qpow(int n,int m){
 17     int s=n,ans=1;
 18     while (m){
 19         if (m&1)ans=1LL*ans*s%mod;
 20         s=1LL*s*s%mod;
 21         m>>=1;
 22     }
 23     return ans;
 24 }
 25 void add(int x,int y){
 26     edge[E].nex=head[x];
 27     edge[E].to=y;
 28     head[x]=E++;
 29 }
 30 void dfs(int k,int fa){
 31     f[k][0]=f[k][1]=1;
 32     for(int i=head[k];i!=-1;i=edge[i].nex)
 33         if (edge[i].to!=fa){
 34             dfs(edge[i].to,k);
 35             int x=f[k][0],y=f[k][1],s=1LL*C3*f[edge[i].to][1]%mod;
 36             f[k][0]=(1LL*x*s+1LL*x*f[edge[i].to][0])%mod;
 37             f[k][1]=(1LL*y*s+1LL*y*f[edge[i].to][0]+1LL*x*f[edge[i].to][1])%mod;
 38         }
 39 }
 40 void ntt(poly &a,int n,int p){
 41     for(int i=0;i<(1<<n);i++){
 42         int s=0;
 43         for(int j=0;j<n;j++)
 44             if (i&(1<<j))s+=(1<<n-j-1);
 45         if (i<s)swap(a.a[i],a.a[s]);
 46     }
 47     for(int i=2;i<=(1<<n);i<<=1){
 48         int s=qpow(3,(mod-1)/i);
 49         if (p)s=qpow(s,mod-2);
 50         for(int j=0;j<(1<<n);j+=i)
 51             for(int k=0,ss=1;k<(i>>1);k++,ss=1LL*ss*s%mod){
 52                 int x=a.a[j+k],y=1LL*ss*a.a[j+k+(i>>1)]%mod;
 53                 a.a[j+k]=(x+y)%mod;
 54                 a.a[j+k+(i>>1)]=(x+mod-y)%mod;
 55             }
 56     }
 57     if (p){
 58         int s=qpow((1<<n),mod-2);
 59         for(int i=0;i<(1<<n);i++)a.a[i]=1LL*a.a[i]*s%mod;
 60     }
 61 }
 62 poly mul(poly x,poly y,int n){
 63     while (x.a.size()<(1<<n+1))x.a.push_back(0);
 64     while (y.a.size()<(1<<n+1))y.a.push_back(0);
 65     for(int i=(1<<n);i<(1<<n+1);i++)x.a[i]=y.a[i]=0;
 66     ntt(x,n+1,0);
 67     ntt(y,n+1,0);
 68     for(int i=0;i<(1<<n+1);i++)x.a[i]=1LL*x.a[i]*y.a[i]%mod;
 69     ntt(x,n+1,1);
 70     while (x.a.size()>(1<<n))x.a.pop_back();
 71     return x;
 72 }
 73 poly Inv(poly a,int n){
 74     if (!n){
 75         poly ans;
 76         ans.a.push_back(qpow(a.a[0],mod-2));
 77         return ans;
 78     }
 79     poly s=Inv(a,n-1),ans=mul(s,a,n);
 80     for(int i=0;i<(1<<n);i++)ans.a[i]=mod-ans.a[i];
 81     ans.a[0]=(ans.a[0]+2)%mod;
 82     return mul(ans,s,n);
 83 } 
 84 poly ln(poly a,int n){
 85     while (a.a.size()<(1<<n))a.a.push_back(0);
 86     poly s=Inv(a,n);
 87     for(int i=1;i<(1<<n);i++)a.a[i-1]=1LL*i*a.a[i]%mod;
 88     a.a[(1<<n)-1]=0;
 89     a=mul(a,s,n);
 90     for(int i=(1<<n)-1;i;i--)a.a[i]=1LL*qpow(i,mod-2)*a.a[i-1]%mod;
 91     a.a[0]=0;
 92     return a;
 93 }
 94 poly exp(poly a,int n){
 95     if (!n){
 96         poly ans;
 97         ans.a.push_back(1);
 98         return ans;
 99     }
100     poly s=exp(a,n-1),ans=ln(s,n);
101     for(int i=0;i<(1<<n);i++)ans.a[i]=(a.a[i]-ans.a[i]+mod)%mod;
102     ans.a[0]=(ans.a[0]+1)%mod;
103     return mul(ans,s,n);
104 }
105 int main(){
106     scanf("%d%d%d",&n,&m,&T);
107     if (!T){
108         for(int i=1;i<n;i++){
109             scanf("%d%d",&x,&y);
110             mat[x][y]=mat[y][x]=1;
111         }
112         int tot=0;
113         for(int i=1;i<n;i++){
114             scanf("%d%d",&x,&y);
115             if (mat[x][y])tot++;
116         }
117         printf("%d",qpow(m,n-tot));
118         return 0;
119     }
120     C1=(qpow(m,mod-2)+mod-1)%mod;
121     C2=1LL*m*C1%mod;
122     C3=1LL*n*qpow(C1,mod-2)%mod;
123     if (T==1){
124         if (!C1){
125             printf("%d",qpow(n,n-2));
126             return 0;
127         }
128           memset(head,-1,sizeof(head));
129         for(int i=1;i<n;i++){
130             scanf("%d%d",&x,&y);
131             add(x,y);
132             add(y,x);
133         }
134         dfs(1,0);
135         f[1][1]=1LL*f[1][1]*C3%mod;
136         printf("%d",1LL*f[1][1]*qpow(C2,n)%mod*qpow(n,mod-3)%mod);
137         return 0;
138     }
139     C3=1LL*C3*n%mod;
140     if (T==2){
141         if (!C1){
142             printf("%d",qpow(n,2*n-4));
143             return 0;
144         }
145         fac[0]=inv[0]=inv[1]=1;
146         for(int i=1;i<N;i++)fac[i]=1LL*fac[i-1]*i%mod;
147         for(int i=2;i<(N<<1);i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
148         for(int i=1;i<(N<<1);i++)inv[i]=1LL*inv[i-1]*inv[i]%mod;
149         a.a.push_back(0);
150         for(int i=1;i<(1<<17);i++)a.a.push_back(1LL*C3*qpow(i,i)%mod*inv[i]%mod);
151         a=exp(a,17);
152         printf("%d",1LL*fac[n]*a.a[n]%mod*qpow(C2,n)%mod*qpow(n,mod-5)%mod);
153         return 0;
154     }
155 }
View Code
原文地址:https://www.cnblogs.com/PYWBKTDA/p/14798183.html