P11426 题解

lmh_qwq · 2025-01-02 13:37:22 · 题解

参考了官方题解。下文称“A 在 B 右边”当且仅当 A 处在 B 往顺时针方向移动一格走到的位置，类似地定义“A 在 B 左边”。

显然直接 dp 是没有前途的，它的极限在 O(n^4)，所以得容斥。考虑算结果的生成函数 F(x)，其中 [x^{n+i}]F(x) 为 i 位置的答案。

将 U=[1,n]\cap \Z 划分为若干个集合 S_1\cdots S_k，对于每个 S_i，强制集合内所有数顺次相连，且这些数按照顺时针方向从小到大排列。不同集合间的顺序不做要求。

例如，如果我们划分出一个集合 \{1,2,4\}，则我们排列选手的方案必须满足 1 右边为 2，2 右边为 4。

或者说，我们固定若干个顺时针方向的单调增的连续段。

对于连续段相接的地方，贡献就是左边的人获胜的贡献。这个贡献可以拆到连续段的头尾处，具体地，开头贡献为 x 当且仅当它是 B，结尾贡献为 x 当且仅当它是 R。否则贡献为 1。

对于被固定的地方，B\to R 贡献为 x-1，R\to B 贡献为 1-x^2，其余情况下贡献为 0。同时这些连续段可以任意排列，最后还要乘一个阶乘。

这玩意看上去没啥道理，所以还是需要解释一下。

任选一个可能的排列，考虑所有可能的选择方式。

“对于没有被固定的地方，贡献就是左边的人获胜的贡献”相当于默认两个连续段相接的地方左边（逆时针方向）那个人赢了，所以开头贡献为 x 当且仅当它是 B，结尾贡献为 x 当且仅当它是 R。

当然我们有可能在胡说八道，右边那个人获胜也是有可能的。但是如果右边的人获胜了，那么一定存在一个强制选择上升段的方案使得其余位置全部相同，但目前出问题的两个人在一个上升段里面（显然有一个一一对应关系）。此时，B\to R 贡献为 x-1，R\to B 贡献为 1-x^2，其余情况下贡献为 0（实际上是 x-x），这是一个正的项和一个负的项相减，负的那玩意减掉的就是胡说八道的情况下凭空变出来的贡献。

现在把这些链放到 1\sim n 的序列上，注意到只有 R,B 交替的链有贡献，所以我们甚至不需要维护每条链，只需要记录 R\to B 和 B\to R 的出现次数即可。最后每一个 R\to B 和 B\to R 的边的集合与有意义的方案一一对应，且它们贡献相同。

准确地说，如果 R\to B 出现了 a 次，B\to R 出现了 b 次，那么它的贡献是 (x-1)^a(1-x^2)^bx^{n-2b}(n-a-b-1)!，证明显然。