ARC061D Card Game for Three

发表于 更新于 分类于 ， ， 阅读次数：

题意：有三堆牌，分别有 张。牌上写着数字 中的一个。

先从牌堆 中抽一张，接下来，牌上写着几就从几号牌堆抽取。

求在所有可能的 种牌堆方案中，先把牌堆 抽空的方案数。

答案对 取模，。

把抽取出的牌排成一个序列 ，显然，每种放置方式都对应一个抽牌序列。（构造映射）

但是，由于可能拿不完牌，所以一个抽牌序列 可能对应很多种牌堆方案，具体地，一个长为 的抽牌序列对应 种牌堆方案，其中 是没有抽出来的牌数。（检查反射）

我们思考对抽牌序列 的约束，如题所述：率先将堆 拿空。（检查充要条件）

于是，问题就变成了：对每个长度 ，求先将堆 拿空的抽牌序列个数，然后乘以 求和。

显然，抽牌序列中一定恰有 个 ，且最后一个必须是 。

枚举抽出的非 牌个数 ，方案数为

解释： 表示 个自由的 与非 混合的方案数，后面的求和是将非 牌分为 和 的方案数。

糟糕的是，后半部分是组合数部分和，这似乎没有什么快速的方法分别独立求解，考虑递推。 求出各个 之后，答案即为 复杂度线性。