冷滟泽的个人博客冷滟泽的个人博客

Luogu 5206. 【WC2019】数树

首先转化题意,对于确定的两棵树,设它们的边集分别为 E_1,E_2,则 E_1\cap E_2 形成了一棵森林,当前方案对答案的贡献为 y 的连通块数次方,即 y^{n-|E_1\cap E_2|}。下面对本题的三问分别讨论。

op=0

这是最简单的一种情况,因为两棵树的形态已知,所以只有一种方案。枚举 E_1 中的每条边,判断其是否在 E_2 中出现即可。

op=1

我们不妨认为 E_1 是已知的,枚举 E_2。设 f(S) 表示 E_1\cap E_2=S 的方案数,则答案为

Ans=\sum_{S\subseteq E_1}y^{n-|S|}f(S)

然而 f(S) 是不好求的,我们定义辅助数组 g(S) 表示 S\subseteq E_1\cap E_2 的方案数,即 E_1E_2 都包含 S 的方案数。这看上去比 S 好计算一些。根据容斥原理,有

f(S)=\sum_{S\subseteq T}(-1)^{|T|-|S|}g(T)

代回答案式并交换求和号,得

\begin{aligned} Ans&=\sum_{S\subseteq E_1}y^{n-|S|}\sum_{S\subseteq T}(-1)^{|T|-|S|}g(T)\\ &=y^n\sum_{T\subseteq E_1}(-1)^{|T|}g(T)\sum_{S\subseteq T}\left(-\frac{1}{y}\right)^{|S|}\\ &=y^n\sum_{T\subseteq E_1}(-1)^{|T|}g(T)\left(1-\frac{1}{y}\right)^{|T|}\\ &=y^n\sum_{T\subseteq E_1}\left(\frac{1}{y}-1\right)^{|T|}g(T) \end{aligned}

到此为止式子已经很简洁了,关键在于 g(T) 的求法。这里涉及到一个小结论:

对于一个 n 个点、k 个连通块的森林,每个连通块的大小分别为 a_1,a_2,\cdots,a_k,将其连成一棵树的方案共有 h(n,k)=n^{k-2}\prod\limits_{i=1}^{k} a_i 种。

下面是一个基于 Prufer 序列的证明:

将每个连通块视为一个点,考虑它们之间连成的树。容易发现在连通块 u,v 间连边的贡献为 a_ua_v,因此如果一个编号 v 在 Prufer 序列中出现了 i 次(即度数为 i+1),则它对答案的贡献为 a_v^{i+1}。考虑到每个节点的原标号是不同的,我们设贡献的 EGF 为 F_v(x),那么 F_v(x)=\sum_{i=0}^{k-1}a_v^{i+1}\frac{x^i}{i!}=a_v e^{a_vx}

\begin{aligned}h(n,k)&=(k-2)![x^{k-2}]\prod_{i=1}^{k} F_i(x)\\&=(k-2)![x^{k-2}]\prod_{i=1}^k a_i e^{a_ix}\\&=(k-2)![x^{k-2}]e^{nx}\prod_{i=1}^k a_i\\&=n^{k-2}\prod_{i=1}^{k}a_i\end{aligned}

也可以用矩阵树定理手解行列式来求证。

回到题目,根据定义,容易看出 g(T)=h(n,n-|T|)。令 a_{T,i} 表示 T 的第 i 个连通块的大小,代入答案式得

\begin{aligned} Ans&=y^n\sum_{T\subseteq E_1}\left(\frac{1}{y}-1\right)^{|T|}n^{n-|T|-2}\prod_{i=1}^{n-|T|}a_{T,i}\\ &=y^n\sum_{j=1}^{n}\left(\frac{1}{y}-1\right)^{n-j}n^{j-2}\sum_{T\subseteq E_1,|T|=j}\prod_{i=1}^{j}a_{T,i}\\ &=y^n\left(\frac{1}{y}-1\right)^{n}n^{-2}\sum_{T\subseteq E_1}\prod_{i=1}^{n-|T|}n\left(\frac{1}{y}-1\right)^{-1}a_{T,i}\\ &=\dfrac{(1-y)^{n}}{n^2}\sum_{T\subseteq E_1}\prod_{i=1}^{n-|T|}\dfrac{ny}{1-y}a_{T,i} \end{aligned}

这个式子就具有一些意义了。我们不妨设 K=\dfrac{ny}{1-y}。抛开前面的常数,后面的东西表示将原树划分成若干个连通块,一个大小为 size 的连通块将产生 K\cdot size 的乘积贡献,求所有方案的贡献和。这显然可以用树形 DP 求:设 dp(u,i) 表示考虑节点 u 的子树,u 所在连通块大小为 i 的贡献和,那么答案为 K\sum\limits_{i=1}^{n}dp(root,i)\cdot i。这样可以做到 O(n^2),不足以通过本题。

我们想办法对 DP 的状态进行一些优化以降低复杂度。考虑去掉第二维,发现仍可以通过某些方法计算贡献。具体地,我们利用每个贡献的组合意义,在当前连通块中加入一个点相当于将答案加上 K 倍的其他连通块的贡献。改设状态为 dp(u,0/1) 表示考虑节点 u 的子树,u 所在连通块是否已做出贡献。转移时考虑加入一个儿子 v,可以写出转移方程

\left\{\begin{array}{l} dp'(u,0)=dp(u,0)dp(v,1)+dp(u,0)dp(v,0)\\ dp'(u,1)=dp(u,1)dp(v,1)+dp(u,1)dp(v,0)+dp(u,0)dp(v,1) \end{array}\right.

答案即为 \dfrac{(1-y)^{n}}{n^2}\cdot dp(root,1)。顺便说一下,这一部分与 CF917D 的处理几乎是相同的。

op=2

与上一问类似,我们写出容斥的式子:

\begin{aligned} Ans&=\sum_{S}y^{n-|S|}f'(S)\\ &=\sum_{S}y^{n-|S|}\sum_{S\subseteq T}(-1)^{|T|-|S|}g^2(T)\\ &=y^n\sum_{T}\left(\frac{1}{y}-1\right)^{|T|}g^2(T)\\ &=\dfrac{(1-y)^n}{n^4}\sum_{T}\prod_{i=1}^{n-|T|}\dfrac{n^2y}{1-y}a_i^2 \end{aligned}

其实唯一的区别就是把 g 换成了 g^2,导致后面的一些项的次数发生了变化。这个式子就不好线性求了,但我们发现「划分连通块」本身就是把 n 个有标号的点放进若干无序的集合中,且每个集合的贡献至于集合大小有关。这一组合意义对应了指数生成函数的 exp,具体地,设

F(x)=\sum_{i=1}^{n}\frac{n^2y}{1-y}i^i\cdot \frac{x^i}{i!}

这是因为大小为 i 的连通块的每个生成树都有 \dfrac{n^2y}{1-y}i^2 的贡献,而 i 个点一共有 i^{i-2} 棵生成树。那么答案为

Ans=\dfrac{(1-y)^n}{n^4}n![x^n]\exp{F(x)}

所以写一个多项式 exp 然后取第 n 项就行了,复杂度 O(n\log n)

这道题有个需要注意的地方就是 y=1 时要特殊处理。对于上面三种情况,此时答案分别为 1,n^{n-2},n^{2(n-2)}

#include <cstdio>
#include <vector>
#include <set>
using namespace std;
const int P=998244353;
int qpow(int n, int k)
{
    int r=1;
    while (k)
    {
        if (k&1) r=1ll*r*n%P;
        n=1ll*n*n%P, k>>=1;
    }
    return r;
}
int n, y, op;
namespace Solver1
{
    void main()
    {
        set<pair<int, int>> edges;
        for (int i=1, u, v; i<n; i++)
        {
            scanf("%d%d", &u, &v);
            if (u>v) swap(u, v);
            edges.insert(make_pair(u, v));
        }
        int cnt=n;
        for (int i=1, u, v; i<n; i++)
        {
            scanf("%d%d", &u, &v);
            if (u>v) swap(u, v);
            if (edges.count(make_pair(u, v))) cnt--;
        }
        printf("%d\n", qpow(y, cnt));
    }
}
namespace Solver2
{
    const int MAXN=100005;
    vector<int> G[MAXN];
    int K, f[MAXN], g[MAXN];
    void DFS(int u, int fa)
    {
        f[u]=K, g[u]=1;
        for (int v: G[u]) if (v!=fa)
        {
            DFS(v, u);
            f[u]=(1ll*f[u]*f[v]+1ll*f[u]*g[v]+1ll*g[u]*f[v])%P;
            g[u]=(1ll*g[u]*f[v]+1ll*g[u]*g[v])%P;
        }
    }
    void main()
    {
        if (y==1) return printf("%d\n", qpow(n, n-2)), void();
        for (int i=1, u, v; i<n; i++)
        {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        K=1ll*n*y%P*qpow(1-y+P, P-2)%P, DFS(1, 0);
        printf("%lld\n", 1ll*f[1]*qpow(1-y+P, n)%P*qpow(n, P-3)%P);
    }
}
namespace Solver3
{
    const int MAXN=1<<18;
    /* poly templates begin */

    /* poly templates end */
    int fac[MAXN], ifac[MAXN];
    int a[MAXN], b[MAXN];
    void main()
    {
        if (y==1) return printf("%d\n", qpow(n, 2*(n-2))), void();
        fac[0]=1;
        for (int i=1; i<=n; i++) fac[i]=1ll*fac[i-1]*i%P;
        ifac[n]=qpow(fac[n], P-2);
        for (int i=n; i>=1; i--) ifac[i-1]=1ll*ifac[i]*i%P;
        int K=1ll*n*n%P*y%P*qpow(1-y+P, P-2)%P;
        for (int i=1; i<=n; i++) a[i]=1ll*K*qpow(i, i)%P*ifac[i]%P;
        poly_exp(a, b, n+1);
        printf("%lld\n", 1ll*b[n]*fac[n]%P*qpow(1-y+P, n)%P*qpow(n, P-5)%P);
    }
}
int main()
{
//  freopen("P5206.in", "r", stdin);
//  freopen("P5206.out", "w", stdout);
    scanf("%d%d%d", &n, &y, &op);
    if (op==0) Solver1::main();
    else if (op==1) Solver2::main();
    else Solver3::main();
    return 0;
}
未经允许不得转载:冷滟泽的个人博客 » Luogu 5206. 【WC2019】数树

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址