洛谷4199 万径人踪灭
Luogu BZOJ 分析 下文中默认字符串的下标从 $0$ 开始。 可以发现答案等于「位置和字符都关于某条对称轴对称的子序列」的数量减去「回文子串」的数量。 后面的就是 manacher 板子，考虑怎么求前面的。 设 $c_i$ 表示「位置和字符都关于对称轴 $i$ 对称的子序列」的数量，则有 后就可以用 FFT 求出 $c_i$ 了。每条对称轴 $i$ 的贡献则为 $2^{c_i}-1...
Luogu BZOJ 分析 下文中默认字符串的下标从 $0$ 开始。 可以发现答案等于「位置和字符都关于某条对称轴对称的子序列」的数量减去「回文子串」的数量。 后面的就是 manacher 板子，考虑怎么求前面的。 设 $c_i$ 表示「位置和字符都关于对称轴 $i$ 对称的子序列」的数量，则有 后就可以用 FFT 求出 $c_i$ 了。每条对称轴 $i$ 的贡献则为 $2^{c_i}-1...
Luogu LOJ 分析 一种 FFT 做法 考虑 DP 。设 $dp_{i,j}$ 表示前 $i$ 个骰子和为 $j$ 的概率。 可以发现转移是一个多项式快速幂，于是直接 FFT 就可以了。 （大概）可以理解成概率生成函数卷积？ 然而 FFT 掉精度很严重，我只能过 $60$ 分。所以对于大数据要考虑其它做法。 一种定积分做法 首先要知道中心极限定理的一个推论： 设有 $n$ 个独立同分...
Luogu LOJ 分析 首先题目要求的其实就是方案数。 设 $cnt_i$ 表示颜色为 $i$ 的珍珠的数量，那么如果一组方案合法的话会有 显然也是一个卷积的形式。 于是只需要构造多项式求出 $f_i$ ，再构造多项式求出 $g_i$ ，再求答案即可。 另外注意特判 $2m<n-D$ 和 $2m>n$ 的情况，答案分别为 $D^n$ 和 $0$ 。 总结：这是一道好题，可是...
Luogu 分析 考虑写出所有物品的生成函数 于是可以调和级数的处理出 $G(x)$，然后多项式 exp 即可。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #i...
Luogu 分析 令 * 为 $0$ ，a 为 $1$ ，以此类推；定义 $dis(A,B)=\sum\limits_{i=0}^{n-1}(A_i-B_i)^2A_iB_i$ 。 显然，当且仅当 $dis(A,B)=0$ 时，$A=B$ 。 将 $dis(A, B)$ 展开得到 将 $A$ 翻转后 FFT 即可。 代码 //It is made by M_sea #include <...
Luogu 分析 显然两个手环增加非负整数亮度，等于其中一个增加一个整数亮度。 设亮度改变了 $c$，则新的差异值为 前面两项是定值；带 $c$ 的两项是关于 $c$ 的二次函数，而且因为 $n>0$，所以有最小值，可以直接算出来；最后一项可以倍长 $a$ 并翻转，然后和 $b$ 卷积即可求出每个旋转角度的值，取个 $\max$ 即可。 代码 //It is made by M_se...