DSU Master：题解

思路

固定前缀长度 $k$。如果 $a_j=0$，边 $j$ 有机会向当前包含顶点 $1$ 的汇点连入一条边；如果 $a_j=1$，它不会产生这种贡献。

记

$f_i$ 表示在只看前 $i-1$ 条边的相对顺序时，顶点 $1$ 在处理边 $i$ 前仍是所在连通块汇点的有效排列数。加入边 $i$ 后：若 $a_i=0$，原有 $i$ 个插入位置都保持汇点，故乘 $i$；若 $a_i=1$，恰有一个插入位置会使顶点 $1$ 不再是汇点，故乘 $i-1$。这正是 $i-a_i$。

令 $ans_i$ 为题目要求的长度为 $i$ 的所有排列的值之和。把新边 $i$ 插入旧排列：旧贡献在 $i$ 个插入位置中各出现一次，得到 $i\,ans_{i-1}$；当且仅当 $a_i=0$ 时，还新增 $f_i$ 条指向顶点 $1$ 的边。因此

两条递推都可在线性时间维护。

做法

满分做法按输入顺序维护 $f$ 与 $ans$。读入 $a_i$ 后，先用当前 $f_i$ 更新并输出 $ans_i$，再计算 $f_{i+1}=f_i(i-a_i)$。

子任务算法

• 子任务 1：枚举每个 $k$ 的全部 $k!$ 个排列，按题意用并查集模拟有向合并。
• 子任务 2：先计算所有 $f_i$，再对每个 $k$ 显式求和 $\sum_{j=1}^k[a_j=0]f_j\,k!/j!$，复杂度 $O(n^2)$。
• 子任务 3：使用上述两个滚动递推，复杂度 $O(n)$。

正确性证明

引理 1：$f_i$ 等于处理边 $i$ 前顶点 $1$ 仍为所在连通块汇点的有效相对顺序数。

证明：$f_1=1$。将边 $i$ 插入已有顺序时共有 $i$ 个位置。若 $a_i=0$，它指向左侧汇点，所有位置都保留顶点 $1$ 为汇点；若 $a_i=1$，恰有一个位置使右侧汇点接管，只有 $i-1$ 个位置有效。因此转移为 $f_{i+1}=f_i(i-a_i)$。归纳成立。

引理 2：$ans_i=i\,ans_{i-1}+[a_i=0]f_i$。

证明：把新边 $i$ 插入每个长度 $i-1$ 的排列，共有 $i$ 个位置，所以既有入边贡献被重复 $i$ 次。新边仅在 $a_i=0$ 且顶点 $1$ 仍为汇点时贡献一条入边，这类排列由引理 1 恰有 $f_i$ 个。故递推成立。

定理：算法输出每个 $k$ 的正确答案。

证明：由引理 2，从 $ans_0=0$ 依次计算得到的 $ans_k$ 恰为全部 $k!$ 个排列的值之和；所有运算按模数进行，不改变模意义答案。

复杂度

每组测试时间复杂度 $O(n)$，空间复杂度 $O(1)$；所有测试合计为 $O(\sum n)$。