World Tour Finals 2022 Day2 D. Cat Jumps

jiangly · 2023-09-10 20:55:06 · 题解

题目大意：把 N 个正整数 A_1,A_2,\ldots,A_N 和 \sum_{i=1}^NA_i 个 -1 任意排列，对每个 k=1,\ldots,N 求有多少种排列方式恰好有 k 个前缀和为 0。

题目中要求把相同的 A_i 看成本质相同的，但是为了方便，我们认为它们都是不同的，最后答案除掉每种 A_i 出现次数的阶乘。

首先做一个容斥，变成钦定 k 个前缀和为 0。再去掉顺序，就是要求把所有数分成 k 个非空集合，每个集合总和都是 0 的方案数。

等价地，就是把 A_i 分成 k 个集合，每个集合的贡献是 (s+1)(s+2)\cdots(s+c)，其中 s 是集合的总和，c 是集合大小。这其实就是 A_i 和对应数量的 -1 排列的方案数。设划分 k 个集合的贡献总和为 f_k。

考虑这个式子的组合意义，就是 i 向 j 连有权值为 A_j+[j\le i] 的边，每个点向集合内连一条边的所有方案的权值乘积的和。（因为集合内编号第 i 小的点向集合内所连的边的总权值为 s+i）

那么现在我们只需要计算每个点出发连一条边形成的图有 k 个连通块的总权值 g_k，那么上述的集合划分就是把这些连通块再进行划分，所以 f_k=\sum_i g_iS_2(i,k)，其中 S_2(i,k) 是第二类斯特林数。

形成的图显然是一个基环内向森林，我们可以再枚举环进行一次容斥。设钦定了 k 个环的图的总权值是 h_k，那么 \sum_{k=0}^N h_kx^k=\sum_{k=0}^Ng_k(x+1)^k。复合 (x+1) 就是因为图中的每个环可以钦定或者不钦定。

现在假设我们钦定了 k 个环，那么环以外的点 j 会让权值乘上 (\sum_{i=1}^NA_i)+j，因为它可以任意连边。环上的边权仍然是 A_j+[j\le i]，我们把它写成 (A_j+1)-[j>i]，把这两部分分别处理。也就是把确定在环上的点划分成若干条编号递增的链，其中链首的权值是 (A_j+1)，其余点的权值都是 -1，之后再把这些链任意划分成环，也就是乘上第一类斯特林数。

到这里就可以 DP 了，设前 i 个点划分出 j 条链的权值为 dp(i,j)，则

对应的三种转移分别是链首、不在环上和选之前的一条链接上去。

总时间复杂度 O(N^2)。