【习题选讲】数学2

imily's notebook

2020-07-20

Flowers and Chocolate

生成函数题，好想做出来啊，，杠了一天半了，只能咕咕

咕咕
题解

求 sum{a_i} < sum{b_i} 的方案数，其中 a_i 和 b_i 有取值范围

考虑到 a_i 和 b_i 有一个下限 l，将柿子化为 sum{l_i + x_i} < sum{l_i + x_i} 的形式，其中 0 <= x_i <= r_i

隔板法 + 容斥即可

看到 n 这么大，模数却只有 1e6 应该想到 lucas 定理啊

m 又是质数，(T^k - (S - T)^k) % m 成一个周期为 m 的数列

然后一发乱搞就好了（

C(Ai + Aj + Bi + Bj, Ai + Aj) 就是求从 (0, 0) 走到 (Ai + Aj, Bi + Bj) 的方案数

移位，变成求从 (-Ai, -Bi) 走到 (Aj, Bj) 的方案数

那么对于每个点，我们计算从它左下区域走上来的方案数之和

显然 dp[i, j] = dp[i - 1, j] + dp[i, j - 1]。坐标值都很小，可以枚举。最后别忘了减去 (-Ai, -Bi) 对 (Ai, Bi) 的贡献。

转化一下就是求已放白球数 >= 已放彩球种类的方案数，容易想到每放一种颜色就把 K 个全放完的想法。

其实真正重要的只有那 n 个白球和那 n 个第一次放下的彩球。dp，f[i, j] 表示已放 i 白球，j 种彩球的方案数。

并不是很难的题，第一步想懂了后面就好办了。

将 a、b、c 的赢看作又抽了一张卡，即 b 抽了第 m + 1 张，c 抽了第 k + 1 张，而 a 抽了第 n 张（a 先手）枚举 a 赢之前 b 和 c 各抽了几张卡，化柿子 + 分类讨论即可。

度数建图，容易想到 prufer 序列，但这是基环树。

定义本题的 prufer 序列为将树删完后的 prufer 序列，只剩下一个环和连着环的编号最大的点。

想到树上节点在 prufer 序列中出现次数为 deg - 1，环上只有一个节点出现次数为 deg - 3，其他都是 deg - 2（特判只有一个环的情况）。

环大小为 k 时，环排列数为 (k - 1)! / 2（环有旋转同构和翻转同构），prufer 序列数为 (n - k + 1)! / prod{ (di - ?)! }

dp计算分母那玩意，f[i, j, k] 表示前 i 个点有 j 个环上点，k 为 0/1 表示是否选了出现次数 deg - 3 的点。

所以最后答案就是 $\sum\limits_{i = 3}^{n - 1} f[n, i, 1] \times (n - i - 1)! \times \frac{(i - 1)!}{2}$

柿子很好列出来，怎么推呢？

指数型生成函数模板题，回去就重修生成函数。