P17786 小糸侑不是罪过 题解

linyicen · 2026-11-10 15:23:56 · 题解

题意

• 称一种构造方案为：给 2 到 n 的每个节点 x 钦定一个父亲 f_x，构造一棵树。
• 定义一棵树的剖分价值为：按编号重剖后形成的若干重链的权值和+链长的乘积。
• 给定每个点的点权 v_i，求这 (n-1)! 种构造方案的剖分价值之和。

分析

• 先将每个点 v_i \gets v_i + 1，去掉链长贡献。
• 无法将乘积式的每一项压入状态，故拆贡献为：每条链选一个点，求所有选法的贡献和，即将和的乘积转化成乘积的和。
• 可以开始 DP 了。考虑倒着做，将建树过程转化成：考虑到 i 时，从 i+1 到 n 的森林中选若干个连通块作为儿子。发现重儿子信息和这个过程都是线性的，很优美，尝试计入状态：f_{i,j,k} 表示考虑到 i，形成 j 个连通块，其中 k 个连通块中从根开始延伸的重链已经选定代表点（对应前面选点）的贡献和。
• 但你发现选哪些连通块不太好刻画，而且转移必须是 3d-3d 的。于是考虑这样一个过程：对于新加入的点，先选好它的一个儿子，然后再从剩余的连通块中选出一些（也可能不选），钦定当前这个儿子和这些连通块的父亲相同，即后续会同时被选。于是前面说的选儿子过程也就变成选一个了，分步转移即可。

代码

转移部分的代码如下。

需要注意：如果当前点要钦定一些兄弟连通块，那么必须保证当前点所在连通块的重链已经决定好，因为它不会成为重儿子。

f[(n + 1) & 1][0][0] = 1;
for (int i = n; i >= 2; i--){
    for (int j = 0; j <= n; j++){
        for (int k = 0; k <= j; k++){
            f[i & 1][j][k] = tmp[0][j][k] = tmp[1][j][k] = 0;
        }
    }
    for (int j = 0; j <= n; j++){
        for (int k = 0; k <= j; k++){
            int pr = f[(i + 1) & 1][j][k];
            if (!pr) continue;
            upd(tmp[0][j][k], pr);
            upd(tmp[1][j][k], 1ll * pr * val[i] % MOD);
            if (j - k >= 1){
                upd(tmp[0][j - 1][k], 1ll * pr * (j - k) % MOD);
                upd(tmp[1][j - 1][k], 1ll * pr * val[i] % MOD * (j - k) % MOD);
            }
            if (k >= 1){
                upd(tmp[1][j - 1][k - 1], 1ll * pr * k % MOD);
            }
        }
    }
    for (int j = 0; j <= n; j++){
        for (int k = 0; k <= j; k++){
            if (tmp[0][j][k]){
                upd(f[i & 1][j + 1][k], tmp[0][j][k]);
            }
            if (tmp[1][j][k]){
                upd(f[i & 1][j + 1][k + 1], tmp[1][j][k]);
                upd(f[i & 1][j][k], 1ll * tmp[1][j][k] * j % MOD);
            }
        }
    }
}
cout << (1ll * f[2 & 1][1][0] * val[1] % MOD + f[2 & 1][1][1]) % MOD << endl;