[Min25筛]2021牛客暑期多校训练营6 G【Hasse Diagram】题解
题目概述Hasse Diagram解题报告考虑 $f(n)$ 的递推式，但是如果只考虑单个素数，很明显会数重复，因此一次性考虑完一个素数，即 $p^k$ 。对于 $n\over p^k$ 的所有...
[生成函数+分治NTT+多项式ln]洛谷4705【玩游戏】题解
题目概述Luogu4705解题报告二项式展开后：$$
{t!\over nm}\sum_{k=0}^{t}{1\over k!}(\sum_{i=1}^{n}a_i^k){1\over(t-k)...
[除法分块+Min25筛]2021 CCPC 威海 I【Distance】题解
题目概述Distance解题报告$i$ 走到 $j$ 不管怎么走，每个相差的素数都必须走一遍，所以...
[NTT]AtCoder Grand Contest 005F【Many Easy Problems】题解
题目概述AGC005F解题报告考虑每个点对 $k$ 的贡献：$$
\sum_{i=1}^{n}[{n\choose k}-\sum_{(i,j)\in E}{size_j\choose k}]=...
Lyndon分解
性质$S$ 是Lyndon串当且仅当 $S$ 本身是所有后缀中的最小串。$S$ 是Lyndon串可以推出 $S$ 是所有循环表示中字典序最小的。各种性质与推论：$A,B$ 都是Lyndon串且 ...
[DP+分治NTT]HDU5322【Hope】题解
题目概述HDU5322解题报告考虑连通块是什么样的，对于 $n$ 的排列，$n$ 所在位置之前的点肯定都是 $n$ 连通块中的，并且 $n$ 没有往后的边。然后对于 $n$ 右边的数列也可以递归...
[容斥+分治NTT]LOJ2541【「PKUWC2018」猎人杀】题解
题目概述LOJ2541解题报告可以把题目转化为，有一个外人向 $n$ 个人开枪，打到第 $i$ 个人的概率是 $w_i\over \sum w$ ，并且可以对死人开枪（但没有效果），问最后才打死...
[分数规划+长链剖分+线段树]洛谷4292【[WC2010]重建计划】题解
题目概述洛谷4292解题报告题解里很多点分治，但其实用长链剖分十分的直白。首先先用01分数规划，二分答案 $mid$ ，然后问题转化为边权为 $w-mid$ 的树上选出一条和 $\ge0$ 且长...
[长链剖分+DP]BZOJ4543【[POI2014]Hotel加强版】题解
题目概述给出一棵树，求多少个 $(a,b,c),a<b<c$ 满足三个点两两距离相同。解题报告考虑以这三个点的LCA $x$ 统计答案，则只有两种情况：在 $x$ 不同儿子 $u,v...
[长链剖分+DP]Codeforces1009F【Dominant Indices】题解
题目概述CF1009F解题报告定义 $f_{i,j}$ 表示 $i$ 子树内到 $i$ 距离为 $j$ 的个数，则显然 $f_{i,0}=1,f_{i,j}=\sum_{u\in son(i)}...
