CF1784D Wooden Spoon

Alex_Wei · 2023-02-07 16:43:07 · 题解

设编号较大的人一定赢过编号较小的人，这与题目条件是相反且对称的。

我们发现特别奖的获奖条件是以递归形式定义的，这启发我们使用动态规划解决该问题。

先确定树的形态：顶部为根，底部为叶子，1\sim n + 1 共 n + 1 层，第 i 层每个点的子树大小为 2 ^ {n - i + 1}。

自顶向下或自底向上考虑。

• 自底向上考虑时，我们需同时记录当前赢家的编号，和当前子树内获得特别奖的编号，无法接受；
• 自顶向下考虑时，每次转移都需要枚举输掉的玩家编号（在本小局中，获胜的玩家编号就是当前赢家编号），最后一步输掉的玩家刚好符合特别奖的要求，可以接受。

通过上述分析，设 f_{i, j} 表示自上而下第 i 层（倒数第 i 轮）的赢家为 j 且它输掉了之后的所有比赛的方案数。根据实际意义，f_{1, j} = [j = 2 ^ n]。

考虑 f_{i, j}\to f_{i + 1, k}（j > k）的贡献系数。我们不关心第 i + 1 层 j 子树形态，其方案数为从 j - 2 ^ {n - i} - 1 个数（1\sim j，除了 j 和第 i + 1 层 k 子树内 2 ^ {n - i} 个数）中选出 2 ^ {n - i} - 1 个数（最后有解释），和 j 一起作为第 i + 1 层 j 的子树内所有点，乘以 2 ^ {n - i}! 表示任意排列。还需要乘以 2 表示第 i + 1 层 j, k 的位置可交换。

注意到贡献系数和 k 无关，因此前缀和优化即可做到 \mathcal{O}(2 ^ nn)。代码。

关于贡献系数中组合数的解释：在 1\sim p_1 中选 q_1 个数，然后在 1\sim p_2 中选 q_2 个数（不能和之前选择的数重复），以此类推，选择之间无序。从限制最严格的 p_1 开始依次考虑，有 \binom {p_1} {q_1} \binom {p_2 - q_1} {q_2} \binom {p_3 - q_1 - q_2} {q_3} \cdots。而整个 DP 过程相当于倒过来考虑这个问题，故有该看似不符合组合意义的转移系数。