如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。
M_sea 的博客
歩み続けて 辿り着く先へと洛谷2612 [ZJOI2012]波浪
Luogu分析考虑拆掉绝对值。对于一个数 $i$，如果它左右两边都比它小则其贡献为 $-2i$，如果一边比它小一边比它大则其贡献为 $0$，如果两边都比它大则其贡献为 $2i$。考虑从小到大插入所有数。设 $f_{i, j, k, l}$ 表示插入了 $1 \sim i$，形成了 $j$ 个连续段，$1 \sim n$ 的贡献之和为 $k$，有 $l$ 个边界已经放了数的方案数。这里我们认为...
洛谷7295 [USACO21JAN] Paint by Letters P
Luogu分析如果我们在相邻的两个相同字符间连一条边，可以发现得到的图为平面图。对于平面图，我们有欧拉公式其中 $F$ 为区域数（无界域也算一个区域）、$V$ 为点数、$E$ 为边数、$C$ 为连通块数。于是我们可以想办法求出 $F, V, E$。$V$ 是好求的，即为 $(x_2 - x_1 + 1)(y_2 - y_1 + 1)$；$E$ 也是好求的，只需要维护二维前缀和即可。下面考虑如...
牛客挑战赛36D 排名估算
牛客分析设 $X$ 为小 C 的排名，$Y$ 为题目条件。那么随便用什么方法算自然数幂和即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include &l...
洛谷5206 [WC2019]数树
LuoguLOJorz 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$ 个点的生成树有 $a...
CF183D T-shirt
CodeforcesLuogu分析考虑对于每一件 T-shirt 计算其贡献。下面设当前考虑的 T-shirt 为 $k$。设 $f_{i, j}$ 表示前 $i$ 个人，有 $j$ 人适合大小为 $k$ 的 T-shirt 的概率，转移为是单减的。因此我们可以每次贪心地找一个 $\Delta g$ 最大的 T-shirt 大小出来。实现时，我们先求出对每个 T-shirt 大小求出 $f_...
洛谷3711 仓鼠的数学题
Luogu分析为了方便我们先令 $y$ 等于 $x + 1$，则 $S_k(x) = \sum_{i = 0}^{y - 1} i ^ k$。根据伯努利数的结论有后面同样是差卷积的形式，翻转后一遍 NTT 即可。代码// ==================================== // author: M_sea // website: https://m-sea-bl...
LOJ6358 前夕
LOJ分析考虑求出交集大小至少为 $k$ 的方案数 $f(k)$，显然有从小到大枚举 $k$，动态维护 $(\omega ^ j - 1) ^ k$ 即可 $\mathcal{O}(n)$ 计算。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ ...
CF1375H Set Merging
CodeforcesLuogu分析考虑对值域分块，设块长为 $B$。对于每块，我们考虑凑出每个原序列中区间对应的集合（这样的集合实际上只有 $\mathcal{O}(B^2)$ 个）。这样子就可以通过把每一块对应的集合合并来得到每个询问的答案了，操作次数为 $\frac{nq}{B}$。考虑每一块内对值域分治，每次将两个子区间 $\mathcal{O}(len^2)$ 地合并，这样子每块操作...
CF1278F Cards
CodeforcesLuoguCF 上评测 ID 是 #108009000，感觉非常的好看（分析为了方便，设 $a = \frac{1}{m}, b = 1 - \frac{1}{m}$。枚举第一张是王牌的次数，答案为预处理斯特林数计算即可。直接递推是 $\mathcal{O}(k ^ 2)$ 的，也可以用 NTT $\mathcal{O}(k \log k)$ 求。代码// =======...
CF734F Anton and School
CodeforcesLuogu分析事实上有 $(a \operatorname{and} b) + (a \operatorname{or} b) = a + b$。那么于是我们可以求出所有 $a_i$ 的和。这里注意判一下 $\sum b_i + c_i$ 是不是 $2n$ 的倍数。接着我们就可以求出每个 $a_i$。这里也要注意判一下 $b_i + c_i - \sum a_i$ 是不是...