洛谷6773 [NOI2020]命运
Luogu LOJ 分析 规定根节点的深度为 $1$。 考虑 DP。设 $dp_{u,i}$ 表示以 $u$ 为根的子树，下端在子树中的未被覆盖的链的上端的最深深度为 $i$ 时的方案数（$i=0$ 表示全部被覆盖）。这个“最深”的好处在于我们覆盖了深的就一定会覆盖浅的，便于计数。 考虑转移，每次把一棵子树合并进来，考虑子树的父边填 $1$ 还是 $0$ 可以得到 可以想到整体 DP，用线...
M_sea 发布的文章
- 首页
- M_sea
洛谷6271 [湖北省队互测2014]一个人的数论
Luogu 分析 先莫比乌斯反演一下 后面那个东西是 $(\mu\cdot \mathbf{id})*\mathbf{id}$，显然是积性函数，所以我们可以对于每个质因子单独计算后乘起来。而对于每个质因子显然只有 $x=1$ 和 $x=p$ 时 $\mu(x)$ 不为 $0$，所以只要算两项即可。 至于 $f_i$，可以求拉格朗日插值公式中每项系数求出，也可以直接高斯消元。 代码 // =...
洛谷6730 [WC2020]猜数游戏
Luogu LOJ 分析 先简单介绍一下阶。设 $\gcd(a,p)=1$，则满足 $a^x\equiv 1\pmod p$ 的最小正整数 $x$ 被称为 $a$ 在模 $p$ 意义下的阶，记做 $\operatorname{ord}_pa=x$ 阶有这样一些性质（这里没有证明，可以自行查找相关资料）： $\operatorname{ord}_p a|\varphi(p)$。于是我们可以枚...
洛谷6772 [NOI2020]美食家
Luogu LOJ 分析 如果见得多的话，从 “恰好第 $T$ 天回到城市 $1$”、$n\leq 50$、$w_i\leq 5$ 和 $T\leq 10^9$ 中不难知道本题要用矩阵快速幂。 这类问题是这样的：边有边权，求从 $i$ 出发经过恰好 $k$ 条边走到 $j$ 的最长路。 对这种题可以想到 DP。设 $dp_{k,i,j}$ 表示从 $i$ 出发经过恰好 $k$ 条边走到 $...
POI2011 简要题解
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...
洛谷3516 [POI2011]PRZ-Shift
Luogu LOJ 分析 假设已经排好了 $1\sim i$，考虑如何把 $i+1$ 放到 $i$ 后面。可以构造出这样的方案： 首先用 ka 把 $i+1$ 移到最前面。 重复使用 2a 1b 把 $i$ 后面的元素两个两个地移到 $i+1$ 和 $1$ 之间。 如果最后 $i+1$ 后面还有一个元素，使用 1a 2b 把它移到 $i+1$ 和 $1$ 之间。 这样子有一个问题，即当 ...
51nod1355 斐波那契的最小公倍数
51nod LOJ 分析 为了方便，下面简记 $f_S$ 为 $f_{a_1},f_{a_2},\cdots,f_{a_k}$，其中 $S=\{a_1,a_2,\cdots,a_k\}$。 考虑一个经典容斥 从小到大枚举倍数算贡献即可。 实现得好的话时间复杂度是 $\mathcal{O}(n\log n)$ 的。 代码 // ================================...
洛谷3700 [CQOI2017]小Q的表格
Luogu LOJ 分析 可以发现这两条规则长得很像更相减损术，推一推可以得到 最后那一步可以考虑实际意义，证明就不写了（ 如果没有修改的话就可以预处理 $i^2\varphi(i)$ 的前缀和然后数论分块计算了。然而现在还有若干次对于 $f(d,d)$ 的修改，可以想到用一个数据结构来维护。 思考一下，我们在数论分块时需要进行 $\mathcal{O}(Q)$ 次修改和求 $\mathc...
洛谷3312 [SDOI2014]数表
Luogu LOJ 分析 先不考虑 $a$ 的限制，则答案为 这样子可以发现，我们只要把 $\leq a$ 的 $\sigma(k)$ 的贡献设成 $\sigma(k)$、$> a$ 的 $\sigma(k)$ 的贡献设为 $0$ 就可以算出正确答案了。 于是只要把所有询问按 $a$ 排序，然后将 $\sigma(k)$ 从小到大加入即可。 代码 // ===============...