CF1707D Partial Virtual Trees

· · 题解

CF1707D Partial Virtual Trees

注意到 S_1 \neq S_2 的限制很烦人，考虑容斥掉。

具体地，令 G(i) 表示答案，F(i) 表示用 i 步使得 U = \{1\} 且不要求相邻两个 U 不等的方案数。

考虑 F(i)，枚举哪几步满足 U 不等，可知 F(i) = \sum\limits_{j = 1} ^ i \dbinom i j G(j)，即从 i 步中选出 j 步不等，剩下来所有步 U 相等，后者方案唯一，故总方案数为 \dbinom i j G(j)。

显然的二项式反演形式，可知 G(i) = \sum\limits_{j = 1} ^ i (-1) ^ {i - j} \dbinom i j F(j)，因此只需求出 F(j)。

回顾虚树的性质：称一个点被点亮当且仅当它为虚树关键点，若 u 的两棵子树 x, y 均存在节点被点亮，则 u 必须点亮。

笔者一开始想设 f_{i, k} 表示 i 子树内恰好在第 k 步变为 \{i\}，发现无法封闭转移。换一种定义方式，设 f_{i, j} 表示 i 子树直到第 j 个时刻还有被点亮的点的方案数。

考虑转移，分 i 在第 k 时刻仍点亮和未点亮两种情况。对于前者，容易发现只要每个子树内合法，i 子树内必然合法，故

f_{i, k} \gets \prod\limits_{u\in son(i)}\sum\limits_{j = 0} ^ k f_{u, j}

容易前缀和优化至 \mathcal{O}(n ^ 2)，设 s_i 为 f_i 的前缀和。

对于后者，枚举 i 在第 p 时刻至第 p + 1 时刻被熄灭，则在 p + 1 时刻到 k 时刻 有且仅有 i 的一个儿子子树被点亮。据此，有转移式

f_{i, k} \gets \sum\limits_{p = 0} ^ {k - 1} \sum\limits_{u\in son(i)} f_{u, k} \prod\limits_{v\in son(i) \land v\neq u} s_{v, p}

改变求和顺序，预处理前后缀积从而预处理 g_{u, p} = \prod\limits_{v \in son(i) \land v \neq u} s_{v, p}，对它做一遍前缀和，那就是

f_{i, k} \gets \sum\limits_{u\in son(i)} f_{u, k} g_{u, k - 1}

同样 \mathcal{O}(n ^ 2) 做，最后 \mathcal{O}(n ^ 2) 做一遍二项式反演即可。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e3 + 5;
int n, mod, f[N][N], s[N][N], g[N][N];
int F[N], C[N][N];
vector<int> e[N], son[N];
void dfs(int id, int ff) {
    f[id][0] = s[id][0] = 1;
    for(int it : e[id]) {
        if(it == ff) continue;
        son[id].push_back(it);
        dfs(it, id);
    }
    for(int k = 0; k <= n; k++) {
        int prod = 1;
        for(int it : son[id]) prod = 1ll * prod * s[it][k] % mod;
        static int pre[N], suf[N];
        int L = son[id].size();
        pre[0] = suf[L + 1] = 1;
        for(int i = 1; i <= L; i++) {
            pre[i] = 1ll * pre[i - 1] * s[son[id][i - 1]][k] % mod;
        }
        for(int i = L; i; i--) {
            suf[i] = 1ll * suf[i + 1] * s[son[id][i - 1]][k] % mod;
            g[son[id][i - 1]][k] = 1ll * pre[i - 1] * suf[i + 1] % mod;
        }
    }
    for(int it : son[id]) 
        for(int k = 1; k <= n; k++)
            add(g[it][k], g[it][k - 1]);
    for(int k = 1; k <= n; k++) {
        int prod = 1;
        for(int it : son[id]) prod = 1ll * prod * s[it][k] % mod;
        add(f[id][k], prod);
        for(int it : son[id]) {
            int coef = f[it][k];
            coef = 1ll * coef * g[it][k - 1] % mod;
            add(f[id][k], coef);
        }
    }
    for(int i = 1; i <= n; i++) {
        s[id][i] = s[id][i - 1];
        add(s[id][i], f[id][i]);
    }
}
void solve() {
    cin >> n >> mod;
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= i; j++) {
            if(!j) C[i][j] = 1;
            else C[i][j] = C[i - 1][j - 1], add(C[i][j], C[i - 1][j]);
        }
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    for(int i = 1; i < n; i++) {
        F[i] = 1;
        for(int it : son[1]) F[i] = 1ll * F[i] * s[it][i - 1] % mod;
    }
    for(int i = 1; i < n; i++) {
        int ans = 0;
        for(int j = 1; j <= i; j++) {
            int coef = 1ll * C[i][j] * F[j] % mod;
            if(i - j & 1) add(ans, mod - coef);
            else add(ans, coef);
        }
        cout << ans << " ";
    }
    cout << endl;
}
int main() {
    int T = 1;
    while(T--) solve();
    return 0;
}