标签 生成函数 下的文章

对于每个联通块,可以看做进出了若干次将其走完,显然可以暴力状压预处理出走 ii \in [1, k] )步将该联通块走完的方案数。题意转换为,有 n 个颜色染若干个格子,相邻两个格子不能同色,某种颜色染了的次数唯一对应一个固定权值,一种方案的权值为每种颜色分别染的次数对应的权值的连乘积。这显然可以通过二项式反演来求。

READ MORE

被同学拉去做其他的题了咕掉了考试

假设用 f(a, b) 表示长度为 a ,有 b 个黑色珠子的且满足首位连接后没有超过 k 个连续黑色珠子的方案数,设 g(x) = f(n / x, m / x) ,可以通过 Burnside 引理证明 ans = \sum\limits_{i=1}^n g(n / \gcd(i, n))

考虑 f(a, b) 相当于求方程组

x_0 + x_1 + ... + x_{a - b} = b(0 \leq x_i \leq k, 0 \leq x_0 + x_{a - b} \leq k)

的解的个数,可以转换为生成函数

READ MORE

题目要求恰好等于 M 的方案数,我们只需要求出小于等于 M 的和小于等于 M-1 的,相减即可。

考虑 Purfer 序列,他的长度为 N - 2,按照题目要求,每个数只能出现 0 ~ M - 1 次,考虑组合生成函数 f(x) = \sum\limits_{i=0}^{m-1} \frac {x^i} {i!} ,那么答案即 (N-2)![x^{N-2}]f^N(x)

READ MORE