题解（本篇仅概述）

 

前言

有进步，只做了半天。。。。

一道具有极强综合性的数数好题！

强大的多合一题目

精确地数学推导和耐心。

有套路又不失心意。

 

融合了：

算法：

prufer序列及其扩展

树形Dp

容斥或者二项式定理

EGF

多项式Exp

 

先要会：

 

然后开始刚题。

就是：

求各种情况下的y^(n-|T1∩T2|)的和

 

 

OP=0

哈希。

OP=1

枚举交集，统计符合的T2树的个数

prufer序列森林版扩展

但是会算重，连回去会多

考虑重组贡献

每个实际的$y^k$会被$k$小的时候计算，$y^k=(y+1-1)^k=∑C(j,i)(y-1)^i$

发现，只要把贡献的$y$成$y-1$，就大功告成啦！

$\Pi szi$可以套路地组合意义成为每个连通块选择一个的方案数，然后就$f[i][0/1]$就O(n)辣

注意每次选择交的边还有贡献

这里，第二个$y^{-1}$运算的时候，要变成$(y^{-1}-1)$

OP=2

还是枚举交集的边

发现和交集大小密切相关，所以枚举交集大小$s$​

然后$gs$设出来，

要枚举边再考虑连通块，不妨枚举连通块考虑贡献的边集

连通块的分配$\frac{n!}{(n-s)!}$,连通块内的连边$a^{a-2}$，连通块之间连边$\Pi a_i *n^{m-2}$

一些东西要平方

把$gs$带回去，然后无关的都提到前面去

把枚举连通块，变成EGF

然后再变成多项式指数函数的形式，大功告成！

 

 

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')using namespace std;typedef long long ll;template
      
       il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
       
        il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
        
         il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
         
          il void prt(T a[],int st,int nd){
   for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{const int N=1e5+5;const int mod=998244353;const int G=3;const int GI=332748118;int n,Y;int mul(int x,int y){
   return (ll)x*y%mod;}int ad(int x,int y){
   return x+y>=mod?x+y-mod:x+y;}il int sub(int x,int y){
   return ad(x,mod-y);}int qm(int x,int y){    int ret=1;    while(y){        if(y&1) ret=mul(ret,x);        x=mul(x,x);        y>>=1;    }    return ret;}namespace sol0{map
          
           
            ,int>mp;int cnt;void main(){ int x,y; for(reg i=1;i
            
             y) swap(x,y);mp[mk(x,y)]=1; } for(reg i=1;i
             
              y) swap(x,y);cnt+=mp[mk(x,y)]; } printf("%d\n",qm(Y,n-cnt));}}namespace sol1{ll f[N][2];int z;int cos,ivc;struct node{ int nxt,to;}e[2*N];int hd[N],cnt;void add(int x,int y){ e[++cnt].nxt=hd[x]; e[cnt].to=y; hd[x]=cnt;}void dfs(int x,int fa){ f[x][0]=f[x][1]=1; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa) continue; dfs(y,x); //jiao and no ll od0=f[x][0],od1=f[x][1]; f[x][0]=ad(mul(od0,f[y][1]),mul(od0,mul(f[y][0],cos))); f[x][1]=ad(mul(od1,f[y][1]),ad(mul(od0,mul(f[y][1],cos)),mul(od1,mul(f[y][0],cos)))); }}void main(){ int x,y; for(reg i=1;i
              

f; Poly(){f.clear();} il int &operator[](const int &x){ return f[x];} il const int &operator[](const int &x) const { return f[x];} il void resize(const int &n){f.resize(n);} il int size() const { return f.size();} il void cpy(Poly &b){f.resize(b.size());for(reg i=0;i<(int)f.size();++i)f[i]=b[i];} il void rev(){reverse(f.begin(),f.end());} il void clear(){f.clear();} il void read(const int &n){f.resize(n);for(reg i=0;i

>1]>>1)|((i&1)?lp>>1:0); } } for(reg i=0;i

>1),t; int m=init(n*2); t.resize(m); for(reg i=0;i

=1;--i){f[i]=mul(f[i-1],qm(i,mod-2));}f[0]=0;return f;}il Poly Diff(Poly f){ int st=f.size();for(reg i=0;i

>1); g.resize(n); g=g*(((Ln(g)*(mod-1))+1)+f); g.resize(n); return g;}il Poly Exp(const Poly &f){ return Exp(f,f.size());}int jie[N],inv[N];void main(){ if(Y==1){ printf("%d\n",mul(qm(n,n-2),qm(n,n-2))); return; } int z=ad(qm(Y,mod-2),mod-1); Poly g; g.resize(n+1); int ivz=qm(z,mod-2); jie[0]=1; for(reg i=1;i<=n;++i) jie[i]=mul(jie[i-1],i); inv[n]=qm(jie[n],mod-2); for(reg i=n-1;i>=0;--i) inv[i]=mul(inv[i+1],i+1); for(reg j=1;j<=n;++j){ g[j]=mul(mul(mul(mul(n,n),ivz),inv[j]),qm(j,j)); } g=Exp(g); ll ans=mul(mul(mul(mul(qm(Y,n),jie[n]),qm(qm(n,mod-2),4)),qm(z,n)),g[n]); cout<