Problem - 1644F - Codeforces 发现第一个操作不是很好考虑，我们优先从第二个操作入手。 如果一个数组 $a_1$ 可以通过操作 $2$ 变成数组 $a_2$ 当且仅当 $a_1$ 中每种颜色的下标集合恰好和 $a_2$ 中一种颜色的集合对应。 也就是意味着我们需要的 $a_1$ 其实不一定要考虑颜色，只需要计算出不同的集合的集合的数量即可。 也就是在 $n$ 中选出 $i$ 个集合，本质就是第二类斯特林数。 之后我们再考虑操作 $1$，显然我们原来多算了答案，对于 $F(a_1, j), j > 1$ 我们发现每个数组都是可能变成一个新的数组，显然存在 $F(a_1, j) = F(a_1, 2j)$ 的情况，就是说明需要容斥来解决。 时间复杂度是 $\sum_{i = 2} ^ n O(\frac{n}{i} \log \frac{n}{i})$ 我们知道调和级数的复杂度是 $O(n \log n)$ 的，那么后面加一个 $\log$ 就是 $O(n \log ^ 2 n)$，可以通过此题。 对于容斥系数的处理，我们可以枚举倍数计 ...

Problem - 1632E2 - Codeforces 首先有一个很直观的解法，发现对于连边肯定是贪心去连最长链到根节点的一条边，之后通过两遍 $\tt dfs$ 来找到答案，复杂度 $O(n)$。 但是上述的解法有很明显的问题： 如何选择最优的最长链？ 为什么不可以连接到两个点的中间？ 我们着重按照这个问题来思考解法。 既然已经知道了肯定是连接根节点的边，我们考虑对于两个深度都大于当前答案 $\tt Ans$ 的点，我们如何才能找到最优的解，设其距离为 $\tt dis$。我们显然可以让两个点的 $d$ 变成 $\tt \lceil\frac{d}{2}\rceil + L$。 就是在路径的中间的某个点连接根节点。 对于所有的这样的点我们都需要考虑一遍吗？ 其实我们只要考虑两棵子树中深度最大的点构成的距离即可。 事实上到这里这个题目就做完了，还有一些细节需要完善，已经明白的大佬可以直接去看代码。 对于这样的两个点，显然深度小的点如果不需要考虑那么对于深度大的点我们可以直接进行连边，所以这个点对生效当且仅当 $\tt Ans$ 小于深度较小的点。 我们显然不需要考虑 ...

多项式计数杂谈 - 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) \\&& ...

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