题目地址 题意： 给定长度为 $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 p ...

题目地址 先拓展一下，对于斐波那契数列也就是 $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}$ 那么我们的式子就是： $$\b ...

[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}) ...

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) &#x ...

如何使用 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}$$ 仔细看看就会发现了左边的分子和右边 ...

退役记 现在是星期天的下午，标题上面的日期已经标记出来了，是我退役之后的第一个周末。 确实是一个很小的角色吧，谁实话就是一个炮灰罢了。 但是毕竟还是有学弟和学妹们的，希望至少为 $XHZX$ 留下一点东西吧。 我是从初一开始接触信息的，已经算比较晚了。仅仅在每个星期五（还不一定有的）社团时间 $2\ hours$。来联系编程。 之后在每天的中午放弃午休的时间进行编程的学习。 运气很好在初二的那一年进入了初赛，以 $90$ 分的成绩。之后显然只有一个 $2=$，毕竟您想想这是浙江呀，仅仅写出来了两题是完全不可能拿到一等的，而刚刚接触的我甚至只知道模拟和贪心，建图也是临时背板子出来的，用的是 $\tt vector$ 的建图（这是我之后和 $\tt vector$ 的情缘的基础）。 当时 $YWZX$ 是只要有普及一等就可以直接面试的，普及二等只是给了一个提前批的名额， 但是我们成绩都还不错都不需要，也算间接为学校提供了一个名额吧。 之后通过奇妙的原因（想知道的可以私信我）考试到了 $HL$，也就是初三的那一年开始正是学习编程。 之前的奖项： 普及二等。 之后开始停课， ...

虚树浅谈 我们就直接进入主题了，毕竟还有 $1 \tt h$ 就要准备去考场了，可能是我退役前的最后一篇学术类的吧。 树上的题目中可能会给出 $\sum k_i \le 5 \times 10^5$ 之类的限制，那么我们常常会考虑到两种东西： 自然根号，也就是本质不同的 $k_i$ 只有 $\sqrt V$ 种。 虚树。 对于给定的一个点集，我们往往不希望这个是一个森林，所以我们钦定加上根节点特判即可。 我们考虑将点集按照 $\tt dfs$ 序进行排序，之后从前向后往栈中加点。我们设 $lc$ 表示当前点和最后加入栈的点的 $\tt Lca$。 如果 $lc = stack(ed)$ 那么意味着还是同样一个子树的链，我们直接加入即可。 不然意味着更换了子树，我们考虑将当前子树的树全部建出，那么因为更换了子树，也就是意味着 $dfn_{lc} \le stack(ed)$ 的，我们考虑退栈直到合法为止。 1while(ed > 1 && dfn[lc] <= dfn[st[ed - 1]]) G.add(st[ed - 1], ...