洛谷6624 [省选联考 2020 A 卷] 作业题
LuoguLOJ分析显然莫比乌斯反演一下，可以得到直接做不一定跑得过去，可以加一个剪枝：如果当前满足条件的边数 $<n-1$ 显然当前的 $d$ 的贡献为 $0$，不必再矩阵树计算。这样子复杂度似乎就是对的了。另外有的高斯消元写法会在生成树个数是 $998244353$ 的倍数的时候 GG，谁能告诉我为啥啊 /kel代码// ==============================...
M_sea 发布的文章
- 首页
- M_sea
洛谷6620 [省选联考 2020 A 卷] 组合数问题
LuoguLOJ分析预处理该处理的东西即可 $\mathcal{O}(m^2)$ 计算。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <b...
洛谷4091 [HEOI2016/TJOI2016]求和
LuoguLOJ分析后面显然是卷积的形式，直接 NTT 即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h&...
洛谷4770 [NOI2018]你的名字
LuoguLOJ分析先考虑 $l=1,r=|S|$ 的情况。对 $S$ 和 $T$ 建 SAM。设 $lim_i$ 表示 $T[1..i]$ 最长的是 $S$ 的子串的后缀的长度，可以在 $S$ 的 SAM 的 Parent 树上跳来求出：如果有对应的转移直接走过去，匹配长度加 $1$；否则跳 Parent 树，直到某个点有对应的转移，匹配长度变为该点的 $len$；如果跳到 $1$ 都没有...
洛谷6190 [NOI Online #1 入门组]魔法
Luogu分析设 $dp_{i,j,k}$ 表示用了 $k$ 次魔法从 $i$ 走到 $j$ 的最小费用。显然有转移足够熟练的话可以看出是一个广义矩阵乘法（将 $+$ 改为 $\min$，将 $\times$ 改为 $+$，仍然满足结合律）的形式，预处理 $dp_{i,j,1}$ 后矩阵快速幂即可。预处理 $dp_{i,j,1}$ 可以先 Floyd 预处理出两两之间的最短路，然后枚举哪条边...
洛谷2178 [NOI2015]品酒大会
Luogu[LOJ](https://loj.ac/problem/2133）分析如果两个位置是 $r$ 相似的，则它们也是 $k\in[0,r)$ 相似的。我们可以只求出 LCP 为 $r$ 时的答案，再求一遍后缀和/后缀 max 即可得到答案。考虑两个位置的 LCP 实际上是一段区间的 $height$ 的最小值。我们可以将 $height_i$ 从大到小排序，每次加入一个 $heigh...
洛谷3757 [CQOI2017]老C的键盘
LuoguLOJ分析为什么 17 年省选还出 13 年的题的弱化版啊设 $dp_{u,i}$ 表示以 $u$ 为根的子树，$u$ 的排名为 $i$ 的方案数。转移时将 $v$ 合并到 $u$ 中，在 $i+j-1$ 个比 $u$ 小的数中选出 $j$ 个放在 $v$ 子树中，在 $sz_u+sz_v-i-j$ 个比 $u$ 大的数中选出 $sz_v-j$ 个放在 $v$ 子树中，即乘上两个组...
洛谷5364 [SNOI2017]礼物
LuoguLOJ分析设 $f_n$ 表示第 $n$ 个人带来的礼物数，$s_n$ 表示 $f_n$ 的前缀和，显然有 $s_n=s_{n-1}+f_n=2s_{n-1}+n^k$。我们只要求出 $s_{n-1}$ 即可求出 $f_n=s_{n-1}+n^k$。考虑矩阵快速幂。这个 $n^k$ 不是很好转移，可以考虑二项式定理可能需要特判 $n\leq 2$ 的情况。代码// ========...
洛谷3934 [Ynoi2016]炸脖龙I
Luogu分析这种题显然要用扩展欧拉定理先考虑没有修改的情况，我们只需要像其它扩展欧拉定理题一样递归下去即可。显然只会递归 $\mathcal{O}(\log p)$ 层，所以复杂度是对的。现在考虑这个修改。我们实际上只需要知道每个位置的值，因此用树状数组实现区间修改、单点查询即可。$\varphi(p)$ 的值显然不能在递归时 $\mathcal{O}(\sqrt{p})$ 求，但是 $p...
洛谷3760 [TJOI2017]异或和
Luogu分析容易想到拆位。则我们需要计算有多少对 $(i,j)$ 满足 $s_j-s_{i-1}$ 的第 $k$ 位是 $1$。那么有两种情况：如果 $s_j$ 的 $0\sim k-1$ 位小于等于 $s_{i-1}$ 的 $0\sim k-1$ 位，则 $s_j$ 和 $s_{i-1}$ 的第 $k$ 位不同时满足条件。否则，$s_j$ 和 $s_{i-1}$ 的第 $k$ 位相同时满...