多项式计数杂谈 - command_block 的博客 学习总结 二项式 $\color{red}(1)$ 拆开组合数 $$\binom{n}{m} = \frac{n!} {m!(n - m)!}$$ 组合意义就是总共有 $n$ 个物品，我们选择 $m$ 个出来的方案数。 根据组合意义，我们需要有 $0 \le m \le n$ 才能保证成立。 一些推论： 对称性 $\binom{n} {m} = \binom{n} {n - m}$ 吸收恒等式 $\binom{n} {m} = \frac{n} {m}\binom{n - 1} {m - 1}$ $\color{red}(2)$ 经典二项式定理 $$(x + y)^k = \sum_{i = 0} ^ k \binom{k}{i}x^iy^{k - i}$$ 注意 $1$ 的幂可能隐藏在求和中。 $\color{red}(3)$ 递推公式 $$\binom{n}{m}= \binom{n - 1}{m} + \binom{n - 1}{m - 1 }$$ 证明的话就是考虑新加入一个数到底是放不放的情况。 ...

首先说一下文章里面木有证明，主要是通过感性理解的方法能更快地了解这个定理。 我们设置换群为 $G$。 轨道稳定集定理 $ord(x) = {g(x), g \in G}$ 表示元素 $x$ 在置换中得到的所有元素的集合。 $sta(x) = {g, g \in G, g(x) = x}$ 表示对于元素 $x$ 所有将其映射到自身的置换。 我们称 $ord(x)$ 为 $x$ 的轨道，$sta(x)$ 为 $x$ 的稳定集。 那么有定理 $|ord(x)||sta(x)| = |G|$。 Burnside 定理我们设 $$s_g(x) =\begin{cases}1, g(x) = x \\0, g(x) \ne x\end{cases}$$ 计数每个 $x$ 不同的轨道数，考虑通过等式进行推出就是： $$\begin{aligned}\sum_{g \in G} \sum_{x \in X} s_g(x) &= \sum_{x \in X} \sum_{g \in G} s_g(x) \\&= \sum_{x \in X} sta(x) \\&= \su ...

题目地址 题意： 给定长度为 $n$ 的数组 $a$，长度为 $m$ 的数组 $p$，其中 $1 \le p_i \le n$ ，而且 $\forall j, p_i \not = p_j$。 在 $p$ 中等概率选定一个非空集合，求 $\sum_{i = 1} ^ n a_i \times |i - p_j|$ 其中 $p_j$ 是选定集合中 $|i - p_j|$ 最小的 $p$。 $m \le n \le 10^5$。 我们考虑先将期望拆分成方案数除以总方案，很显然总方案就是 $2^m - 1$。 然后我们发现对于每一个数 $a_i$ 本质上是没有影响的，我们只需要计算后面部分总共贡献的次数就好了。 再者我们发现 $m$ 是很大的，所以肯定是不能枚举和子集有关的东西了，那么我们可以考虑将数组 $p$ 表示成 $\sum_{i = 1} ^ n [i \in P]$ 的形式。 根据以上的发现我们可以直观感受到这个肯定是和卷积有关的形式。 如果是一个卷积，我们肯定是需要将数组翻转，我们不妨考虑用 $i + j = 2\times pos $ 的形式表示最终的位置。 我们考 ...

题目地址 先拓展一下，对于斐波那契数列也就是 $f_0 = 1, f_1 = 1, f_i = f_{i - 1} + f_{i - 2}, i \ge 2$。 那么有 $\sum_{i = 0} ^ n f_i = f_{n + 2} - 1$ 如果说是 $\sum_{i = 1} ^ n f_i = f_{n + 2} - 2$。 具体来说就是考虑用 $f_{n + 2}$ 进行展开即可。 我们回到题目，考虑题目要求出的式子 $\sum_{i = 1} ^ n f_i^k$。 我们考虑对于 $f_i$ 有通向公式 $f_i = \frac{\sqrt 5}{5} (\frac{1 + \sqrt 5}{2} - \frac{1 - \sqrt 5}{2})^ i$ 为了方便我们设 $a = \frac{1 + \sqrt 5}{2}, b = \frac{1 - \sqrt 5}{2}, c = \frac{\sqrt 5}{5}$ 那么我们的式子就是： $$\begin{aligned}Ans &= \sum_{i = 1} ^ n f_i ^ k \\&= \s ...

[TJOI2015] 概率论 题目地址 首先考虑将期望变成每种方案的叶子总数除以所有的方案。 那么我们不妨先考虑所有的方案需要怎么算，也就是 $n$ 个节点二叉树的数量。 不妨设 $f(n)$ 表示上述的量，可以得到方程 $f(n) = \sum_{i = 0} ^ {n - 1} f(i) \times f(n - 1 - i)$，其中 $f(0) = 1$。 那么我们可以得到生成函数 $F(x) = F^2(x) \times x+ 1$。 之后解得 $F(x) = \frac{1 \pm \sqrt{1 - 4x}}{2x}$。 我们将上面的东西向下除就可以得到 $\frac{2}{1 \pm \sqrt{1 - 4x}}$ 将 $f(0) = 1$ 带入可以得到下面取到的是 $+$，那么上面的就是 $-$。 所以我们可以得到 $F(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$。 我们将其展开可以得到 $\frac{1}{2x} \times (1 - \sqrt{1 - 4x})$。 $$\begin{aligned}F(x) &= \fr ...

BZOJ3684 大朋友和多叉树 题目地址 首先考虑一下如果进行 $\tt Dp$ 的话需要如何进行转移。 考虑单独增加一个节点。 考虑通过题目给出的一个度数进行合并。 但是发现转移的话可能会产生一个环，那么我们就尝试使用$\tt\color{red}\text{生成函数}$，设 $F(x)$ 表示最终答案的生成函数。 那么我们根据之前的转移就可以得到方程： $$F(x) = x + \sum_{i \in Deg} F^i(x)$$ 我们考虑移项得到 $F(x) - \sum_{i \in Deg} F^i(x) = x$ 我们注意到这个最后这个 $x$ 貌似可以进行拉格朗日反演。 设 $G(x) = x - \sum_{i \in Deg} x^i$ 那么我们就有 $G(F(x)) = x$。带入反演的式子得到： $$[x^n]F(x) = \frac{1}{n}[x^{-1}]\frac{1}{G^n(x)}$$ 那么问题来了我们现在多项式能做是表示整式，显然这个 $G(x)$ 是没有逆元的。 因为 $G(0) = 0$。 那么这个就一定是一个分式。我们考虑将其用整 ...

如何使用 Gitbash 首先你需要一个下载地址。 然后我们来和自己的 $\tt github$ 账号进行连接，使用 $\tt SSH$。 我们一下的操作都是在 $\tt gitbash$ 里面进行，也就是鼠标右键出现的那里进去的。 首先检查自己电脑的 $\tt SSHkey$ 是否存在 $ cd ~/.ssh 然后使用 $ ls -al 检查是否存在。 如果连文件夹都不存在的话那肯定是没有的。 如果你需要创建一下 $\tt SSHkey$ 的话，我们使用 $ ssh-keygen -t rsa -C your-email 然后一直回车就可以了。 $\tt your-email$ 就是直接输入你的邮箱。 然后我们找到你保存的文件地址，将 $\tt public$ 的部分复制下来。 我们点到 $\tt github$ 的主页，鼠标放在头像下面，点击 $\tt setting$ 点击 $\tt SSH$ 设置，加入新的钥匙，名字就随便取了，把之前的部分复制在下面的框里。 之后我们检查一下 ssh -T git@github.com 如果成功了就可以了。 然后我们使用 git ...

Link with Balls 给出 $2n$ 个箱子，可以从第 $2x-1$ 箱子取 $kx$ 个球，可以从第 $2x$ 箱子取至多 $x$ 个球，那么最终取 $m$ 个球有几种方法。 每 $n$ 个箱子是本质相同的，我们可以考虑使用生成函数进行计算。 设 $f_i(x) = \sum_{j = 0} ^ i x^j = \frac{1 - z^{i + 1}}{1 - z}$。 设 $g_i(x) = \sum_{j \ge 0} x^{i\times j} = \frac{1}{1 - x^i}$。 之后我们的答案就是 $\prod_{i = 1} ^ n f_i(x) \prod_{i = 1} ^ n g_i(x) = F(x)$。 $$F(x) = \prod_{i = 1} ^ n \frac{1 - x^{i + 1}}{1 - x} \times \prod_{i = 1} ^ n \frac{1}{1 - x^i}$$ 仔细看看就会发现了左边的分子和右边下面是可以抵消的。 之后就会化成 $F(x) = \frac{1}{(1 - x)^{n + 1}} - \f ...