题解：P17856 [LBA-OI R6 D] 奶龙游戏

· · 题解

update on 11.8：感谢 @A_small_WA 老师的提醒，修改了一处笔误。

🦅

上午刚在模拟赛 T3 写了到反射容斥下午怎么就看到了这样的题目。

我们考虑对每个元素所属划分为 A,B，那么 A 标记为 +1，B 则是 -1。

也就是说我们从 (0,0) 出发，最终跑了 2n 步之后跑到了 (2n,0)。

先不考虑这个怎么做，先考虑对于一个划分，我们从大到小计算前缀和，分别记录 mx=\max sum_i,mn=\min sum_i。

思考一下这两个东西的含义，我们能够知道 A 胜出的下界就是 mx，而上界则是 mn+n。

通过调整法证明 mx\sim mn+n 的每个数都能被拼出。

也就是说 mx \le k \le n+mn。

也就是对于这个前缀和数组 sum，如果对 k 有贡献，当且仅当 k-n \le sum_i \le k。

画个图，大概是这个样子。

这个是总图，可以根据具体情况画水平线作为限制。

旋转 45° 就是反射容斥经典形式了。

然后看上去就可以反射容斥来做了，但是注意到这样一个事情：我们不可能既超过上限又超过下限，因为这超出了 n 步的限制。

也就是说我们容斥一下就好了，这么简单？

总方案数 \binom{2n}{n}，非法是 \binom{2n}{n-k-1}+\binom{2n}{k-1}，减一下再求概率就好了。

哎 \dots T3 被卡 \dots