【题解】「WC2019」数树 生成函数+多项式 Exp loj2983 —Qiuly

于由Qiuly发布

题目传送门 qwq

$op=0$

考虑如果一条边在 $(u,v)$ 在红蓝两树中都出现过的话，意味着将 $u,v$ 两点看作一个整体进行染色，故答案为：
$$
y^{n-|T_1\cap T_2|}
$$
其中 $T_1$ 表示蓝树的边集，$T_2$ 表示红树的边集。

期望得分 $28\ pts$ (怎么这么多……)

$op=1$

答案为：
$$
\sum_{T_2}y^{n-|T_1\cap T_2|}
$$
直接枚举 $T_2$ 的话可以过 $n\leq 5$ ，期望得分 $8$ ，同样 $y=1$ 的点很好做，期望得分 $4$ ，总得分 $12$ 。

（然后就有 $40\ pts$ 了喵喵喵？

考虑化简：
$$
\begin{aligned}
\sum_{T_2}y^{n-|T_1\cap T_2|}&=y^n\sum_{T_2}y^{-|T_1\cap T_2|}\\
&=y^n\sum_{S}y^{-|S|}\sum_{T_2} [T_2\cap T_1=S]\\
\end{aligned}
$$
设：
$$
F(S)=\sum_{T_2} [T_2\cap T_1=S]\\
G(S)=\sum_{T_2} [T_2\cap T_1\supseteq S]\\
f(S)=y^{-|S|}F(S),g(s)=y^{-|S|}G(S)\\
$$
则有：
$$
G(S)=\sum_{S\subseteq T} F(T)\\
F(S)=\sum_{S\subseteq T} G(T)\cdot (-1)^{|T|-|S|}\\
F(S)y^{-|S|}=\sum_{S\subseteq T}y^{|T|-|S|}\cdot G(T)y^{-|T|}\cdot (-1)^{|T|-|S|}\\
f(S)=\sum_{S\subseteq T}g(T)\cdot (-y)^{|T|-|S|}\\
$$
答案为：
$$
\sum_{S}\sum_{S\subseteq T}g(T)\cdot (-y)^{|T|-|S|}\\
\sum_{T}\sum_{S\subseteq T}g(T)\cdot (-y)^{|T|-|S|}\\
\sum_{T}g(T)\cdot (-y)^{|T|}\sum_{S\subseteq T}(-y)^{-|S|}\\
\sum_{T}g(T)\cdot (-y)^{|T|}\sum_{i=0}^{|T|}{|T|\choose i}(-y)^{-i}\\
$$
后面凑一个 $1^{|T|-i}$ 然后二项式定理：
$$
\sum_{T}g(T)\cdot (-y)^{|T|}\sum_{i=0}^{|T|}{|T|\choose i}(-\frac{1}{y})^i(1)^{|T|-i}\\
\sum_{T}g(T)\cdot (-y)^{|T|}(1-\frac{1}{y})^{|T|}\\
\sum_{T}G(T)\cdot y^{-|T|}\cdot (-y)^{|T|}(1-\frac{1}{y})^{|T|}\\
\sum_{T}G(T)\cdot (-1)^{|T|}(1-\frac{1}{y})^{|T|}\\
\sum_{T}G(T)\cdot (\frac{1}{y}-1)^{|T|}\\
$$
考虑如何求 $G(T)$ 。其实可以发现只需要保证红树中一定存在这 $T$ 集合中的边，其他边任意即可，毕竟 $G$ 的定义是 $[T_2\cap T_1\supseteq S]$ ，所以不用管其他的边。

设 $a_i$ 表示连接了边集 $T$ 中的所有边后，第 $i$ 个连通块的大小。可以将一个连通块看作一个点，这样剩下的方案书可以直接套用 $\rm{Prufer}$ 的公式：

若当前有 $n$ 个点，$m$ 个连通块，每个连通块大小为 $a_i$ 那么加入若干条边后使得 $n$ 个点变为一棵树的方案数为：
$$
res=n^{m-2}\prod_{i=1}^{m}a_i
$$

于是：
$$
G(T)=n^{n-|T|-2}\left(\prod_{i=1}^{n-|T|}a_i\right)
$$
然后代入到上面的式子中：
$$
\sum_{T}G(T)\cdot (\frac{1}{y}-1)^{|T|}\\
\sum_{T}n^{n-|T|-2}\cdot\left(\prod_{i=1}^{n-|T|}a_i\right)\cdot (\frac{1}{y}-1)^{|T|}\\
\sum_{T}n^{n-|T|-2}\cdot(\frac{1}{\frac{1}{y}-1})^{n-|T|}\cdot (\frac{1}{y}-1)^{n}\cdot\left(\prod_{i=1}^{n-|T|}a_i\right)\\
\sum_{T}(\frac{n}{\frac{1}{y}-1})^{n-|T|}\cdot \frac{(\frac{1}{y}-1)^{n}}{n^2}\cdot\left(\prod_{i=1}^{n-|T|}a_i\right)\\
\frac{(\frac{1}{y}-1)^{n}}{n^2}\sum_{T}(\frac{n}{\frac{1}{y}-1})^{n-|T|}\cdot\left(\prod_{i=1}^{n-|T|}a_i\right)\\
\frac{(\frac{1}{y}-1)^{n}}{n^2}\sum_{T}\left(\prod_{i=1}^{n-|T|}\frac{a_in}{\frac{1}{y}-1}\right)\\
$$
现在考虑 $\rm{DP}$ ，设 $dp(i,j)$ 表示考虑到了 $i$ 点，$i$ 点所在连通块大小为 $j$ ，转移的时候考虑一下儿子即可。如果对于当前枚举的儿子不和 $i$ 一个连通块，意味着儿子所在的连通块不可能再变大了，计算一下贡献即可，否则像背包一样合并答案即可，时间复杂度 $O(n^2)$ 。

考虑优化，显然一个连通块只需要选择一个点，在这个点的位置上乘上 $\frac{n}{\frac{1}{y}-1}$ 的贡献即可。

设 $dp(u,1/0)$ 表示 $u$ 子树中，$u$ 所在连通块是否已经做出贡献的方案数。转移的话枚举 $u$ 的儿子 $v$ ，考虑 $(u,v)$ 选还是不选：

  • 如果选：
    • 贡献已经在 $v$ 给出了。
    • 贡献没在 $v$ 给出，但是之前在 $u$ 给出了。
    • 贡献没在 $v$ 给出，但是之前也没有在 $u$ 给出。
  • 如果不选：
    • $v$ 一有贡献，$u$ 的贡献已经给出。
    • $v$ 一定有贡献，$u$ 的贡献还没有给出。

分别对应：
$$
\begin{cases}
dp(u,1)=dp(u,0)\times dp(v,1)\\
dp(u,1)=dp(u,1)\times dp(v,0)\\
dp(u,0)=dp(u,0)\times dp(v,0)\\
dp(u,1)=dp(u,1)\times dp(v,1)\\
dp(u,0)=dp(u,0)\times dp(v,1)\\
\end{cases}
$$
初始化很显然：
$$
\begin{cases}
dp(u,0)=1\\
dp(u,1)=\frac{n}{\frac{1}{y}-1}\\
\end{cases}
$$
时间复杂度 $O(n)$ ，总期望得分 $64\ pts$ 。

需要注意的是由于之前的答案柿为：
$$
y^n\sum_{S}y^{-|S|}\sum_{T_2} [T_2\cap T_1=S]
$$
而我们现在求出来的是：
$$
\sum_{S}y^{-|S|}\sum_{T_2} [T_2\cap T_1=S]
$$
所以最后记得乘上 $y^n$ ！

$op=2$

显然上面那个容斥函数可以拿下来继续用，答案为：
$$
\sum_{T}G^2(T)\cdot (\frac{1}{y}-1)^{|T|}\\
\sum_{T}\left(n^{n-|T|-2}\left(\prod_{i=1}^{n-|T|}a_i\right)\right)^2\cdot (\frac{1}{y}-1)^{|T|}\\
\sum_{T}n^{2n-2|T|-4}\prod_{i=1}^{n-|T|}a_i^2\cdot (\frac{1}{y}-1)^{|T|}\\
\sum_{T}n^{2n-2|T|}n^{-4}\cdot(\frac{1}{\frac{1}{y}-1})^{n-|T|}\cdot (\frac{1}{y}-1)^{n}\prod_{i=1}^{n-|T|}a_i^2\\
\frac{(\frac{1}{y}-1)^{n}}{n^4}\sum_{T}\left(\prod_{i=1}^{n-|T|}\frac{a_i^2n^2}{\frac{1}{y}-1}\right)\\
$$
乘上 $y^n$ 后，最终的答案为：
$$
\frac{(1-y)^{n}}{n^4}\sum_{T}\left(\prod_{i=1}^{n-|T|}\frac{a_i^2n^2}{\frac{1}{y}-1}\right)\\
$$
然后考虑设 $val=\frac{n^2}{\frac{1}{y}-1}$ ：
$$
\frac{(1-y)^{n}}{n^4}\sum_{T}\left(\prod_{i=1}^{n-|T|}a_i^2val\right)\\
$$
于是后面的那一些可以理解为：一个大小为 $x$ 的树其权值为 $x^2val$ 。

构造指数型生成函数，设 $f(x)$ 的 $i$ 次项表示一颗大小为 $i$ 的树的权值。由于一颗大小为 $i$ 的树的方案数为 $i^{i-2}$ ，那么这些数的贡献和就是 $(x^2val)\times(i^{i-2})=i^ival$ ，于是：
$$
f(x)=\sum_{i=0}^{\infty} \frac{i^ival}{i!}
$$
然后考虑设 $g(x)$ 的 $i$ 次项表示有若干棵树，这些树的大小之和 $i$ 的贡献和。

由于森林是由若干棵树拼接而成的，所以有：$g=e^f$ ，$f=\ln g$ 。

可以发现上面的 $\sum_{T}\left(\prod_{i=1}^{n-|T|}a_i^2val\right)$ 其实就是求的有若干棵树，这些树大小之和为 $n$ 的贡献和……

做一遍 $\rm{Exp}$ 后乘上之前的 $\frac{(1-y)^{n}}{n^4}$ 即为答案。

最后需要注意

需要特判 $y=1$ 的点，答案很显然是树的个数，对于 $op=1$ 来说是 $n^{n-2}$ ，对于 $op=2$ 来说是 $n^{2n-4}$ 。

很恶心的就是你需要 $op=1,2,3$ 分别写 $\rm{SubTask}$ ，使得代码有点长……

细节很多，所有的柿子全部都是上文中提到的，用了很多 $mul,add,dec$ 所以可能有点难看，稍微凑合吧 qwq

Code：

#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define mul(x,y) (1ll*x*y%mod)
#define add(x,y) (x+y>=mod?x+y-mod:x+y)
#define dec(x,y) (x-y<0?x-y+mod:x-y)

const int N=4e5+2;
const ll mod=998244353;
int n,y,op;

inline int modpow(int x,int y,int res=1) {
    for(;y;y>>=1,x=mul(x,x)) if(y&1) res=mul(res,x);
    return res;
}
template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

namespace SubTask1 {
    #define MKP make_pair
    map <pair<int,int>,int> M;
    inline void Main() {
        int u,v,res=n;
        for(int i=1;i<n;++i) IN(u),IN(v),M[MKP(u,v)]++,M[MKP(v,u)]++;
        for(int i=1;i<n;++i) IN(u),IN(v),res-=M[MKP(u,v)];
        printf("%d\n",modpow(y,res));
    }
}

namespace SubTask2 {
    int tmp,val,f[N],g[N],cnt,head[N];
    struct Edge {int nxt,to;} G[N<<1];
    inline void addedge(int u=0,int v=0) {
        IN(u),IN(v);
        G[++cnt]=(Edge){head[u],v},head[u]=cnt,
        G[++cnt]=(Edge){head[v],u},head[v]=cnt;
    }
    void dfs(int u,int fa) {
        f[u]=1,g[u]=tmp;
        for(int i=head[u],v;i;i=G[i].nxt) if((v=G[i].to)!=fa) {
            dfs(v,u);
            g[u]=add(mul(f[u],g[v]),add(mul(g[u],f[v]),mul(g[u],g[v]))),
            f[u]=add(mul(f[u],g[v]),mul(f[u],f[v]));
        }
    }
    inline void Main() {
        for(int i=1;i<n;++i) addedge();
        if(y==1) {printf("%d\n",modpow(n,n-2));return;}
        tmp=mul(n,modpow(dec(modpow(y,mod-2),1),mod-2));
        val=mul(modpow(dec(modpow(y,mod-2),1),n),modpow(mul(n,n),mod-2));
        dfs(1,0);
        printf("%d\n",mul(g[1],mul(val,modpow(y,n))));
    }
}

namespace SubTask3 {
    namespace Poly {
        int filp[N],A[N],B[N],C[N],D[N],H[N];
        inline void NTT(int*f,int len,short inv) {
            int cnt=0,limit=1;
            while(limit<len) limit<<=1,++cnt;
            for(int i=0;i<limit;++i)
                filp[i]=(filp[i>>1]>>1)|((i&1)<<(cnt-1));
            for(int i=0;i<limit;++i)
                if(i<filp[i]) swap(f[i],f[filp[i]]);
            for(int p=2;p<=limit;p<<=1) {
                int len=p>>1,tmp=modpow(3,(mod-1)/p);
                for(int k=0;k<limit;k+=p) {
                    int buf=1;
                    for(int l=k;l<k+len;++l,buf=mul(buf,tmp)) {
                        int t=mul(f[l+len],buf);
                        f[l+len]=dec(f[l],t),f[l]=add(f[l],t);
                    }
                }
            }
            if(inv==1) return;
            int sl=modpow(limit,mod-2);reverse(f+1,f+limit);
            for(int i=0;i<limit;++i) f[i]=mul(f[i],sl);
        }
        void Inv(int*f,int*g,int len) {
            if(len==1) return (void)(g[0]=modpow(f[0],mod-2));
            Inv(f,g,len>>1);
            for(int i=0;i<len;++i) A[i]=f[i],B[i]=g[i];
            NTT(A,len<<1,1),NTT(B,len<<1,1);
            for(int i=0,l=(len<<1);i<l;++i) A[i]=mul(A[i],mul(B[i],B[i]));
            NTT(A,len<<1,-1);
            for(int i=0;i<len;++i) g[i]=dec(add(g[i],g[i]),A[i]);
            for(int i=0,l=(len<<1);i<l;++i) A[i]=B[i]=0;
        }
        inline void Direv(int*f,int*g,int len) {
            for(int i=1;i<len;++i) g[i-1]=mul(f[i],i);g[len-1]=0;
        }
        inline void Inter(int*f,int*g,int len) {
            for(int i=1;i<len;++i) g[i]=mul(f[i-1],modpow(i,mod-2));g[0]=0;
        }
        inline void Ln(int*f,int*g,int len) {
            Direv(f,C,len),Inv(f,D,len);
            NTT(C,len<<1,1),NTT(D,len<<1,1);
            for(int i=0,l=(len<<1);i<l;++i) C[i]=mul(C[i],D[i]);
            NTT(C,len<<1,-1),Inter(C,g,len<<1);
            for(int i=0,l=(len<<1);i<l;++i) C[i]=D[i]=0;
        }
        void Exp(int*f,int*g,int len) {
            if(len==1) return (void)(g[0]=1);
            Exp(f,g,len>>1),Ln(g,H,len),H[0]=dec(f[0]+1,H[0]);
            for(int i=1;i<len;++i) H[i]=dec(f[i],H[i]);
            NTT(H,len<<1,1),NTT(g,len<<1,1);
            for(int i=0,l=(len<<1);i<l;++i) g[i]=mul(g[i],H[i]);
            NTT(g,len<<1,-1);
            for(int i=len,l=(len<<1);i<l;++i) g[i]=H[i]=0;
        }
    }using namespace Poly;
    int tmp,fac,f[N],g[N],inv[N];
    inline void Main() {
        if(y==1) {printf("%d\n",modpow(n,2*n-4));return;}
        int val=mul(mul(n,n),modpow(dec(modpow(y,mod-2),1),mod-2));
        inv[0]=inv[1]=tmp=fac=1;
        for(int i=2;i<=n;++i) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod,fac=mul(fac,i);
        for(int i=1;i<=n;++i) tmp=mul(tmp,inv[i]),f[i]=mul(modpow(i,i),mul(val,tmp));
        int len;for(len=1;len<=n;len<<=1);
        Exp(f,g,len);
        int res=mul(modpow(dec(1,y),n),modpow(modpow(n,4),mod-2));
        int ans=mul(mul(res,fac),g[n]);
        printf("%d\n",ans);
    }
}

int main() {
    IN(n),IN(y),IN(op);
    if(op==0) SubTask1::Main();
    else if(op==1) SubTask2::Main();
    else SubTask3::Main();
    return 0;
}
分类： 文章

Qiuly

QAQ

2 条评论

[该用户已被删除] · 2020年1月1日 10:21 上午

学弟都好厉害啊୧(๑•̀◡•́๑)૭

回复

回复 [该用户已被删除] 取消回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注