当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

对于两棵树 T_1, T_2,定义它们的交 T_1 \cap T_2 是它们的边集的交形成的森林,k(T_1 \cap T_2)表示这个森林的连通块个数,求下列三种问题之一:

  1. 给定 T_1, T_2,求 y^{k(T_1\cap T_2)}

  2. 给定 T_1,求 \sum_{T_2}y^{k(T_1\cap T_2)}

  3. 给定 n,求 \sum_{T_1}\sum_{T_2}y^{k(T_1\cap T_2)}

其中 n \leq 10^5 ,上面的 sum 是对所有 n^{n-2} 种可能的树求和。答案对 998244353 取模。

orzrqy

op = 0

两棵树的形态已经给定,考虑一条路径的颜色相同等价与要求每一条同时存在的边的端点颜色相同。

假设第一棵树的边集为 E_1 ,第二棵树的边集为 E_2 ,那么 \displaystyle ans = y^{|E_1 \cap E_2|}

可以直接做,复杂度 O(n \log n)

op = 1

考虑枚举第二棵树,那么

ans = \sum_{E_2} y^{|E_1 \cap E_2|}

考虑枚举 S \subseteq E_1 \cap E_2 容斥计算贡献

ans = \sum_{E_2} \sum_{S \subseteq E_1 \cap E_2} \sum_{P \subseteq S} (-1)^{|S|-|P|} y^{n-|P|}

定义 g(S) 为所有包含边集 S 的生成树个数,这样可以避免枚举 E_2

\begin{aligned} ans &= \sum_{S \subseteq E_1} g(S) \sum_{P \subseteq S} (-1)^{|S|-|P|} y^{n-|P|} \\ &= \sum_{S \subseteq E_1} g(S) y^{n-|S|} \sum_{P \subseteq S} (-y)^{|S|-|P|} \end{aligned}

考虑 \displaystyle{\sum_{P \subseteq S} (-y)^{|S|-|P|}} 如何计算

\begin{aligned} & \sum_{P \subseteq S} (-y)^{|S|-|P|} \\ =& \sum_{|P|=0}^{|S|} \binom {|P|} {|S|} (-y)^{|S|-|P|} \\ =& \sum_{|P|=0}^{|S|} \binom {|P|} {|S|} 1^{|P|} \times (-y)^{|S|-|P|}\\ =& (1-y)^{|S|} \end{aligned}

考虑 g(S) 如何计算,边集 S 会使原图形成 n - |S|(设为 m)个联通块。考虑 Prufer 序列计数

\begin{aligned} g(S) &= \sum_{\{d_i\}} \dfrac {(m-2)!} {\prod_{i=1}^m (d_i-1)!} \prod_{i=1}^m a_i^{d_i} \\ &= \left( \prod_{i=1}^m a_i\right) \times \left( \sum_{\{d_i\}} \dfrac {(m-2)!} {\prod_{i=1}^m (d_i-1)!} \prod_{i=1}^m a_i^{d_i-1} \right) \\ &= \left( \prod_{i=1}^m a_i\right) \times n^{m-2} \\ &= n^{m-2} \prod_{i=1}^m a_i \end{aligned}

那么

ans = \sum_{S \subseteq E_1} n^{n-|S|-2} y^{n-|S|} (1-y)^{|S|} \prod_{i=1}^{n-|S|} a_i

为了方便处理,我们转换一下,以 S \subseteq E_1 放到树上的 DP

ans = n^{-2} (1-y)^n \sum_{S \subseteq E_1} \prod_{i=1}^{n-|S|} \left( \frac {ny} {1-y} \right) a_i

发现 \displaystyle{\prod_{i=1}^{n-|S|} a_i} 即从每个联通块中选出一个点的方案数。

用 DP ,假设 f_{i, 0/1} 表示第 i 个点选 / 没选的方案数。

op = 2

考虑现在的答案

\begin{aligned} ans &= \sum_{S} g^2(S) (1+y)^{|S|} y^{n-|S|} \\ &= \sum_{S} (1+y)^{|S|} y^{n-|S|} \left( n^{n-|S|-2} \prod_{i=1}^{n-|S|} a_i \right)^2 \\ &= \sum_{S} (1+y)^{n - \left( n - |S|\right) } y^{n-|S|} n^{2n-2|S|-4} \prod_{i=1}^{n-|S|} a_i^2 \\ &= \frac {(1-y)^{n}} {n^4} \sum_{S} \prod_{i=1}^{n-|S|} \frac {n^2 y}{1-y} a_i^2\\ \end{aligned}

\displaystyle{k = \frac {n^2 y}{y+1}} ,那么题意转换为

  • 一个树的权值为一个常数 k 乘上它大小的平方
  • 一个森林的权值为其中每一棵树的权值之积
  • 求对于每一种森林的权值之和

考虑用多项式 \exp 解决。

可以考虑把 城市规划 一题的结论推广:假设一个无向图的权值为所有连通块的权值之积,求带标号无向图的权值之和。那么无向图的权值的指数生成函数即联通图权值的指数生成函数的多项式 \exp

更加容易理解一点,假设 f_n 表示 n 个点的无向图权值和,g_n 表示 n 个点的连通图权值和

f(x) = \sum_{i=0}^\infty \frac {f_i x^i} {i!} \\ g(x) = \sum_{i=0}^\infty \frac {g_i x^i} {i!}

那么

f(x) = \exp g(x) \\ g(x) = \ln f(x)

可以泰勒展开下 \exp 来证明,此处不多叙述。

故由题意 \displaystyle{g_i = \left( \frac {n^2y} {y+1} i^2\right) i^{i-2}} = \frac {n^2 i^i y} {y+1} ,写成生成函数的形式:

\begin{aligned} g(x) &= \sum_{i=0}^\infty \frac {n^2 i^i y} {i! (1-y)} x^i \\ &= \sum_{i=0}^\infty \frac {n^2y} {1-y} \times \frac {i^i} {i!} \times x^i \end{aligned}

对其求多项式 \exp 得到 f(x) ,那么答案即

ans = \frac {(1-y)^{n} \times n![x^n]f(x)} {n^4}

代码:

// =================================
//   author: memset0
//   date: 2019.04.08 07:22:47
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
#define debug(...) ((void)0)
#ifndef debug
#define debug(...) fprintf(stderr,__VA_ARGS__)
#endif
namespace ringo {
inline char read() {
    static const int IN_LEN = 1000000; static char buf[IN_LEN], *s, *t;
    return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template <class T> inline void read(T &x) {
    static bool f; static char c;
    for (f = 0, c = read(); !isdigit(c); c = read()) { f ^= c == '-'; if (c == -1) return; }
    for (x = 0; isdigit(c); c = read()) x = ((x + (x << 2)) << 1) + (c ^ '0');
    if (f) x = -x;
}
const int OUT_LEN = 10000000; char obuf[OUT_LEN], *ooh = obuf;
inline void print(char c) {
    if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf;
    *ooh++ = c;
}
template<class T> inline void print(T x) {
    static int buf[30], cnt;
    if (!x) { print('0'); return; }
    if (x < 0) print('-'), x = -x;
    for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + '0';
    while (cnt) print((char)buf[cnt--]);
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }
template <class T> inline void print(T x, char c) { print(x), print(c); }

const int N = 1e5 + 10, mod = 998244353;
int n, m, opt;

inline int dec(int a, int b) { a -= b; return a < 0 ? a + mod : a; }
inline int sub(int a, int b) { a += b; return a >= mod ? a - mod : a; }
inline int mul(int a, int b) { return (ll)a * b - (ll)a * b / mod * mod; }
inline int inv(int x) { return x < 2 ? 1 : mul(mod - mod / x, inv(mod % x)); }
inline int fpow(int a, int b) { int s = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) s = mul(s, a); return s; }

namespace sol1 {
int cnt;
std::set <int> set[N];

int main() {
    for (int i = 1, u, v; i < n; i++) read(u), read(v), set[u].insert(v);
    for (int i = 1, u, v; i < n; i++) read(u), read(v), cnt += set[u].count(v);
    return fpow(m, n - cnt);
}

} // end namespace sol1

namespace sol2 {
int k, f[N][2];
std::vector <int> G[N];

void dfs(int u, int fa = 0) {
    // printf("dfs %d %d | %d\n", u, fa, G[u].size());
    f[u][0] = 1, f[u][1] = k;
    for (auto v : G[u]) if (v != fa) {
        dfs(v, u);
        f[u][1] = sub(mul(f[u][0], f[v][1]), mul(f[u][1], sub(f[v][0], f[v][1])));
        f[u][0] = mul(f[u][0], sub(f[v][0], f[v][1]));
    }
}

int main() {
    if (m == 1) return fpow(n, n - 2);
    for (int i = 1, u, v; i < n; i++) read(u), read(v), G[u].push_back(v), G[v].push_back(u);
    k = mul(inv(dec(1, m)), mul(n, m)), dfs(1);
    // for (int i = 1; i <= n; i++) print(f[i][0], " \n"[i == n]);
    // for (int i = 1; i <= n; i++) print(f[i][1], " \n"[i == n]); 
    return mul(f[1][1], mul(inv(mul(n, n)), fpow(dec(1, m), n)));
}

} // end namespace sol2

namespace sol3 {
int tmp, fac[N], ifac[N], w[N << 2], rev[N << 2];

struct poly : std::vector <int> {
    using std::vector <int> ::vector;
    void in() { for (int i = 0; i < size(); i++) read(at(i)); }
    void out() const { for (int i = 0; i < size(); i++) print(at(i), " \n"[i == size() - 1]); }
} f, g;

inline int init(int len) {
    int lim = 1, k = 0; while (lim < len) lim <<= 1, ++k;
    for (int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
    for (int wn, len = 1; len < lim; len <<= 1) {
        wn = fpow(3, (mod - 1) / (len << 1)), w[len] = 1;
        for (int i = 1; i < len; i++) w[i + len] = mul(w[i + len - 1], wn);
    } return lim;
}

void ntt(int *a, int lim) {
    for (int i = 0; i < lim; i++) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
    for (int len = 1; len < lim; len <<= 1)
        for (int i = 0; i < lim; i += (len << 1))
            for (int j = 0; j < len; j++) {
                int x = a[i + j], y = mul(w[j + len], a[i + j + len]);
                a[i + j] = sub(x, y), a[i + j + len] = dec(x, y);
            }
}

inline poly operator * (const poly &f, const poly &g) {
    static int a[N << 2], b[N << 2]; poly h(f.size() + g.size() - 1);
    int lim = init(h.size()), inv_lim = inv(lim);
    for (int i = 0; i < lim; i++) a[i] = i < f.size() ? f[i] : 0;
    for (int i = 0; i < lim; i++) b[i] = i < g.size() ? g[i] : 0;
    ntt(a, lim), ntt(b, lim);
    for (int i = 0; i < lim; i++) a[i] = mul(a[i], b[i]);
    std::reverse(a + 1, a + lim), ntt(a, lim);
    for (int i = 0; i < h.size(); i++) h[i] = mul(a[i], inv_lim);
    return h;
}

using ringo::inv;
inline poly inv(const poly &f) {
    static int a[N << 2], b[N << 2];
    poly g(1, inv(f[0]));
    for (int len = 2; (len >> 1) < f.size(); len <<= 1) {
        int lim = init(len << 1), inv_lim = inv(lim);
        for (int i = 0; i < lim; i++) a[i] = i < f.size() && i < len ? f[i] : 0;
        for (int i = 0; i < lim; i++) b[i] = i < g.size() ? g[i] : 0;
        ntt(a, lim), ntt(b, lim);
        for (int i = 0; i < lim; i++) a[i] = mul(a[i], mul(b[i], b[i]));
        std::reverse(a + 1, a + lim), ntt(a, lim);
        for (int i = len >> 1; i < len; i++) g.push_back(dec(0, mul(a[i], inv_lim)));
    } g.resize(f.size()); return g;
}

inline poly ln(poly f) {
    poly g(f.size());
    for (int i = 1; i < f.size(); i++) g[i - 1] = mul(f[i], i);
    g = inv(f) * g, g.resize(f.size()), f[0] = 0;
    for (int i = 0; i < f.size() - 1; i++) f[i + 1] = mul(g[i], inv(i + 1));
    return f;
}

inline poly exp(const poly &f) {
    poly g(1, 1), h, t;
    for (int len = 2; (len >> 1) < f.size(); len <<= 1) {
        g.resize(len), h = ln(g), t.resize(len), h.resize(len);
        for (int i = 0; i < len; i++) h[i] = dec(i < f.size() ? f[i] : 0, h[i]);
        for (int i = 0; i < len; i++) t[i] = i < g.size() ? g[i] : 0;
        h[0] = sub(h[0], 1), h = h * t, g.resize(len);
        for (int i = len >> 1; i < len; i++) g[i] = h[i];
    } g.resize(f.size()); return g;
}

int main() {
    if (m == 1) return fpow(n, 2 * n - 4);
    fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
    for (int i = 2; i <= n; i++) fac[i] = mul(fac[i - 1], i);
    for (int i = 2; i <= n; i++) ifac[i] = mul(mod - mod / i, ifac[mod % i]);
    for (int i = 2; i <= n; i++) ifac[i] = mul(ifac[i - 1], ifac[i]);
    g.resize(n + 1), tmp = mul(inv(dec(1, m)), mul(m, mul(n, n)));
    for (int i = 1; i <= n; i++) g[i] = mul(tmp, mul(ifac[i], fpow(i, i)));
    f = exp(g);
    return mul(inv(fpow(n, 4)), mul(fpow(dec(1, m), n), mul(fac[n], f[n])));
}

} // end namespace sol3

void main() {
    read(n), read(m), read(opt);
    if (opt == 0) print(sol1::main(), '\n');
    if (opt == 1) print(sol2::main(), '\n');
    if (opt == 2) print(sol3::main(), '\n');
}

} signed main() {
#ifdef MEMSET0_LOCAL_ENVIRONMENT
    freopen("1.in", "r", stdin);
#endif
    return ringo::main(), ringo::flush(), 0;
}

巧妙的思路 purfer 序列 多项式指数函数 树形 DP

2019 ZJU 校赛垫底记
上一篇 «
洛谷5293 [HNOI2019]白兔之舞
» 下一篇