Luogu3726 [AH2017/HNOI2017] 抛硬币

题意：Alice 抛 次硬币，Bob 抛 次硬币，分别得到 次正面，若 ，则 Alice 获胜。求她获胜的方案数。

答案对 取模，多组数据，，，，，时限 。

---

• 前置芝士：范德蒙德卷积

此时两人是平等的，但是获胜条件并不平等，要刨掉平局的情况 根据范德蒙德卷积 除此之外两人就五五开了，方案数是

注意到 都很大， 却很小，我们需要使用抵消思想才能利用到 。

将抛硬币的结果记载为 01 序列 。（1 代表正面）

• 记 为 中 1 的个数。

• 记 为：将 01 取反得到的序列。

• 称 为 的对偶方案。

显然，我么把所有方案分成了一个个对子。我们希望有很多对子是一胜一负，这样它们就能对消。

当 时，只要 ，对子一定是一胜一负，故我们只用关心 的方案数。

当 时，设 赢一次输一次的对子个数为 （对偶），赢两次的对子个数为 （不对偶）。（显然 不可能一次都不赢）则答案为 又知道 ，故我们只需要在 中求出其一。

直觉告诉我们，由于 很小，不对偶远少于对偶的情况。故我们考虑计算 .

对子不对偶时，按照定义有 且 即 。

出现了！！

分别枚举 可得：（注意，每个对子会被统计两次）

注意到 ，这是个范德蒙德卷积。

使用 次 ExLucas 计算这些组合数。复杂度。

注： 在 下没有逆元，为了除 ，我们把模数乘 再把最后结果直接除 即可。