[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)}...
[分治+矩乘NTT]2022牛客暑期多校训练营（加赛）L【Lndjy and the mex】题解
题目概述Lndjy and the mex解题报告首先不难发现长度为 $len$ 的区间的方案数是相同的，因此只需要考虑区间长度而不需要考虑区间位置（乘 $n-len+1$ 即可）。然后考虑长度...
[Palindrome Series+exgcd]HDU6320【Cut The String】题解
题目概述HDU6320解题报告暴力想法：枚举 $L$ 开始的回文串 $A$ ，和 $R$ 结尾的回文串 $B$ ，如果 $|A|+|B|=R-L+1$ 则找到一个满足的位置。由于是枚举结尾回文串...
[思维+Palindrome Series]Codeforces932G【Palindrome Partition】题解
题目概述CF932G解题报告首先原题意有点恐怖，我们需要进行一定的转化。原题意需要分成偶数个串，然后前后对称相同，如果我们把串的后一半翻转，那么就会发现前后对应的两个字符串是互相翻转的。进一步转...
[链分治+分治NTT]LOJ6289【花朵】题解
题目概述LOJ6289解题报告这题显然是一个树形背包 $f_{x,j,0},f_{x,j,1}$ 表示 $x$ 没选 / 选了，子树里选了 $j$ 个的方案数。这个背包可以写成多项式形式，$B_...
[离线+后缀自动机+LCT]2022牛客暑期多校训练营（加赛）C【Cmostp】题解
题目概述Cmostp解题报告建出SAM，考虑离线，每次添加一个前缀节点 $p_i$ 的时候，就是把 $p_i$ 到 $fail$ 树根路径上的节点的最右终止端点改为 $i$ 。查询 $[L,R]...
