LOJ3399 「2020-2021 集训队作业」Communication Network
LOJ 分析 感觉和 WC2019 数树 的 $op = 1$ 基本一致，如果不会可以戳 这里。 我们还是套用 $\displaystyle |S| \prod_{i = 1}^k na_i$ 有着清晰的组合意义：从 $S$ 中选择一条边，再从每个连通块中选择一个点，每个点产生 $n$ 的乘积贡献。我们要求所有 $S$ 的贡献的总和。 考虑 DP。设 $f_{u, 0/1, 0/1}$ ...
标签 二项式定理 下的文章
- 首页
- 二项式定理
洛谷5206 [WC2019]数树
Luogu LOJ orz laofu！!1 分析 $op = 0$ 只需要统计两棵树有多少条重边即可。假设有 $c$ 条，答案即为 $y^{n - c}$。 $op = 1$ 先特判掉 $y = 1$ 的情况，答案为 $n^{n - 2}$。 我们要求的是 考察每个连通分量。一个大小为 $a$ 的连通分量会产生 $\frac{n^2 y}{1 - y} a^2$ 的乘积贡献，而 $a$...
洛谷3711 仓鼠的数学题
Luogu 分析 为了方便我们先令 $y$ 等于 $x + 1$，则 $S_k(x) = \sum_{i = 0}^{y - 1} i ^ k$。 根据伯努利数的结论有 后面同样是差卷积的形式，翻转后一遍 NTT 即可。 代码 // ==================================== // author: M_sea // website: https://m...
LOJ6358 前夕
LOJ 分析 考虑求出交集大小至少为 $k$ 的方案数 $f(k)$，显然有 从小到大枚举 $k$，动态维护 $(\omega ^ j - 1) ^ k$ 即可 $\mathcal{O}(n)$ 计算。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog...
CF156D Clues
Codeforces Luogu 分析 我们把每个连通块看成一个点，然后用 Prufer 序列计数。那么方案数为 用并查集求出连通块个数及每个连通块的大小即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ============...
洛谷6620 [省选联考 2020 A 卷]组合数问题
Luogu LOJ 分析 预处理该处理的东西即可 $\mathcal{O}(m^2)$ 计算。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include...
洛谷5401 [CTS2019]珍珠
Luogu LOJ 分析 首先题目要求的其实就是方案数。 设 $cnt_i$ 表示颜色为 $i$ 的珍珠的数量，那么如果一组方案合法的话会有 显然也是一个卷积的形式。 于是只需要构造多项式求出 $f_i$ ，再构造多项式求出 $g_i$ ，再求答案即可。 另外注意特判 $2m<n-D$ 和 $2m>n$ 的情况，答案分别为 $D^n$ 和 $0$ 。 总结：这是一道好题，可是...