标签 生成函数 下的文章

\forall i \in [1, n] ,连续性随机变量 f[i][0, 1] 范围内生成,\forall i < j, f_i < f_j 存在一条 i \leftrightarrow j 的双向边,求联通块的大小的期望乘积。

READ MORE

有一个 n 个数的序列,每一个数在 1 \dotsc D 中随机生成,定义一个序列是合法的当且仅当能取出至少 m 个对子(相同的数),对于 D^n 种可能的序列,求合法序列数。D \leq 10^5, n, m \leq 10^9

羡慕你们能去 CTS 的 [大哭]

READ MORE

对于每个联通块,可以看做进出了若干次将其走完,显然可以暴力状压预处理出走 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

f_i 表示 i 个时的高度之和, g_i 表示 i 个时的方案数,显然:

\begin{aligned} g_n &= \sum\limits_{i=1}^n {n \choose i} g_{n-i} \\ f_n &= g_n + \sum\limits_{i=1}^n {n \choose i} f_{n-i} \\ ans_n &= f_n \times g_n^{-1} \end{aligned}

其实到这里可以直接分治 NTT ,不过我们考虑多项式求逆的做法。 首先把 {n \choose i} 拆开,然后设 F_n = f_n / n!G_n = g_n / n!H_n = 1 / n!

\begin{aligned} G &= (2 - H)^{-1} \\ F &= (G - 1) (2 - H)^{-1} \\ ans_n &= F_n G_n^{-1} \end{aligned}

(推导时需要注意常数项系数,f_0 = 0,g_0 = h_0 = 1。)

READ MORE