题解：CF1942G Bessie and Cards

· · 题解

对不起 这句话打乱了时区\ 你要我 在最爱的时候睡去\ 我越想越清醒

发现 b 毫无意义。

先把这三种卡内部排序，之后计数认为同种卡没有区别的方案数，最后答案 \times \frac{a!\times c!\times 5!}{(a+c+5)!}。

考虑如何 check 一个卡牌序列 不 合法。

维护一个变量 s 表示还能摸的牌数，初始 s=5，把特殊卡视作 0 牌。

对于 0 牌，有 s\gets s-1；对于 2 牌，有 s\gets s+1。

当 s=0 时，此时若没摸到五张特殊牌就 不 合法。

我们发现方案形如在格路上走。具体来说，初始在点 (0,5)，要走到点 (x,0)。在点 (i,j) 时可以走到 (i+1,j+1) 或 (i+1,j+1)。在路径中不能碰到直线 y=0。

枚举 x 表示 第一次 碰到 y=0。设 a'=\frac{x+5}{2},c'=\frac{x-5}{2}，表示向下走的次数和向上走的次数，经典反射容斥可得方案数为 {x-1\choose a'-1}-{x-1\choose a'}，然后五张特殊牌都不在前 a' 张牌的方案数为 {a+5\choose 5}-{a'\choose 5}，后面乱排的方案数是 {a+c+5-x\choose c-c'}。全部乘起来即可。

时间复杂度 O(a+c)。