LOJ6538 烷基计数 加强版 加强版
LOJ 分析 要求的就是每个节点的儿子数都不超过 $3$ 的无标号有根树数。 设其 OGF 为 $F(x)$，考虑列出一个关于 $F(x)$ 的方程。 不妨规定 $[x^0]F(x) = 1$，那么可以看成每个节点的儿子数都恰好为 $3$。 直接得出 $F(x) = 1 + F(x) ^ 3$ 显然是错误的，因为我们同构的情况被重复计算了。 因此可以考虑 Burnside 引理。对于 $(1...
分类 题解 下的文章
- 首页
- 题解
洛谷2791 幼儿园篮球题
Luogu 分析 显然进的球数服从超几何分布，即 $\mathcal{O}(L \log L)$ 预处理一行第二类斯特林数，然后 $\mathcal{O}(SL)$ 计算答案即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==...
UOJ188 【UR #13】Sanrd
UOJ 分析 题目要求的就是 $[l,r]$ 中的数的次大质因子的和，这里的次大是可重集的次大。 首先对其差分，变为求 $[1, n]$ 中的数的次大质因子之和。 这个数据范围启发我们考虑一些筛法，仔细思考之后发现只能考虑 Min_25 筛。 然而直接做显然是不行的。我们需要对其第二部分即求答案的部分进行一些改造，使得它能求出我们想求的东西。 对于一个合数，我们在其剩余的质因子个数 $\le...
LOJ6682 梦中的数论
LOJ 分析 可以发现答案即为 数论分块计算即可。 再考虑 $\sum \sigma_0\!^2(i)$。我们知道 $\sigma_0\!^2$ 是积性函数，且有 $\sigma_0\!^2(p) = 4$、$\sigma_0\!^2(p ^ k) = (k + 1) ^ 2$，因此可以使用 Min_25 筛计算。 代码 // ===============================...
BZOJ3684 大朋友和多叉树
darkbzoj 分析 设答案的 OGF 为 $F(x)$，则有 多项式求逆 + 多项式快速幂计算即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #in...
洛谷5406 [THUPC2019]找树
Luogu LOJ 分析 转化为计数问题，求每种权值的生成树个数。 考虑矩阵树定理 我们对每条边构造一个多项式 $f(x)=x^w$，并将乘法定义为输入的运算，这样子求出的基尔霍夫矩阵删去一行一列后的行列式的 $x^w$ 项系数即为边权和为 $w$ 的生成树个数。 具体实现时，我们先对行列式中的每个元素做 FWT，求出行列式后再 IFWT 回来。这里的 FWT 和 IFWT 是广义的，即这...
JOISC2020 部分题解
先放一点上来，剩下的慢慢更。 ビルの飾り付け 4 / Building 4 不难想到一个 $\mathcal{O}(n^2)$ 的 DP：设 $f_{i, j, 0/1}$ 表示前 $i$ 个数选了 $j$ 个 A，最后一个是 A/B 是否可行，转移显然。最后逆序构造方案即可。 可以发现对于某个 $i, 0/1$，为真的 $j$ 一定是一段区间，因此我们只需要维护这段区间，即可去掉 $j$ ...
UOJ551 【UNR #4】校园闲逛
UOJ 分析 设 $f_{i ,j, w}$ 为从 $i$ 走到 $j$、权值和为 $w$ 的方案数，$g_{i, j, w}$ 表示连接 $i,j$ 的权值为 $k$ 的边数。 那么有 可以证明 $I-G$ 一定是可逆的。于是我们只需要求一个每个元素都是一个多项式的矩阵的逆，和普通矩阵求逆类似地做即可。 然而这题还卡常，需要精细地实现来减少 NTT 的次数，最好把预处理原根、取模优化、寻...
洛谷4827 [国家集训队] Crash的文明世界
Luogu 分析 预处理斯特林数和阶乘，换根 DP 求出后面的东西即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/s...
洛谷3773 [CTSC2017]吉夫特
Luogu LOJ 分析 由 Lucas 定理可以推出，${n\choose m}\bmod 1\equiv{2}$ 当且仅当 $n \& m = m$。这样子很容易有一个 $\mathcal{O}(n^2)$ 的 DP。 为了方便，我们倒过来 DP，则要求上一个数是这一个数的子集，直接枚举子集转移即可。 复杂度是 $\mathcal{O}(3^{\log A})$ 的。 代码 //...