如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。
M_sea 的博客
Delightful洛谷5296 [北京省选集训2019]生成树计数
Luogu分析根据二项式定理有所以我们只要把边权设成 $e^{a_ix}$，然后直接矩阵树定理即可。因为数据范围很小，所以多项式乘法和求逆可以直接暴力，NTT 甚至会慢。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==========...
CF1172E Nauuo and ODT
CodeforcesLuogu分析考虑计算每种颜色的贡献，即计算每种颜色包含在多少条路径中。这个东西似乎还是不好算，可以考虑计算每种颜色不包含在多少条路径中。我们把这种颜色染成白色，其它颜色染成黑色，那么只有黑色连通块内部的点对才满足条件。于是我们需要支持修改颜色、求黑色连通块大小平方和，使用 QTREE6 一题的方法把颜色放到父边上，LCT 维护子树信息即可。具体细节可以看一看官方题解中的...
洛谷5326 [ZJOI2019]开关
LuoguLOJ分析设 $P=\sum_{i=1}^n p_i$。设 $F(x)$ 为按到目标状态的指数型概率生成函数，$G(x)$ 为按回自己的指数型概率生成函数。$F(x)$ 直接把每个开关乘在一起即可，$G(x)$ 相当于是 $s_i=0$ 时的 $F(x)$。那么有直接计算即可。代码// ==================================== // author...
洛谷4705 玩游戏
Luogu分析答案显然是直接分治把所有 $1-a_ix$ 卷起来，然后多项式 $\ln$ + 多项式求导即可求出 $G(x)$，再推回 $A(x)$ 后卷积即可。代码不想写 vector，于是从鱼那里蒯了一个分治 /kel// ==================================== // author: M_sea // website: https://m-sea...
AGC038E Gachapon
AtCoderLuogu分析我不喜欢容斥，我不喜欢组合意义，我不喜欢生成函数，我也没有精神首先 Min-Max 容斥一手转移直接枚举 $d$ 即可。为了方便我们把容斥系数压到 DP 里去，转移要乘上一个 $-1$。算答案就把上面这个东西代回去就好了。代码// ==================================== // author: M_sea // websit...
JOISC2018 部分题解
高速道路の建設 / Construction of Highway这个操作长得很像 LCT 中的 access。于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n)$ ...
AGC035D Add and Remove
AtCoder分析可以发现题目中的贡献只有加，按照鸡贼的话来说这是一个很罕见的性质。倒着看整个过程，相当于每次往里面加一个数。我们考虑每个数对答案的贡献。假设当前有若干个数，第 $i$ 个数的贡献是 $x_i$，那么我们在 $i,i+1$ 中加一个数，新加的数的贡献显然是 $x_i+x_{i+1}$。这个 $i,i+1$ 对应原序列中的一段区间，因此可以 DP。设 $dp_{l,r,xl,x...
CF578F Mirror Box
CodeforcesLuogu分析我们把顶点黑白染色，那么一面镜子就可以看成是连接同色点的一条边。接下来给出一个结论：一个方案合法当且仅当黑点连成了一棵树或者白点连成了一棵树。（比较感性理解的）证明：首先，当黑点连边确定时白点连边一定唯一确定，所以我们只考虑黑边确定的情况。先证必要性：先考虑后面那个限制。如果连成了环，则环内部的边一定没有光线会穿过，所以不能有环。再考虑前面那个限制。我们需要...
LOJ150 挑战多项式
LOJ分析无。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freo...