zhangxixi的博客

NTT总结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132591415 https://www.luogu.com.cn/problem/P3803 公式： ωn1≡gp−1n(modp)\large\omega_n^1\equiv g^{\frac {p-1}n}\pmod p ωn1​≡gnp−1​(modp) 然后所有单位根运算都可以转成原根了！（前提 ppp 为质数） ppp 常为 998244353，它的原根 ggg 为 3 实现细节： ...

多项式乘法（FFT） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132588646 https://www.luogu.com.cn/problem/P3803 傅里叶变换(FFT)笔记存档 FFT代码上的实现细节 主函数 把长度设为2的整数次幂块 初始进行翻转（二进制翻转） 对A，B先化为点值（DFT） 相乘 IDFT FFT函数 进行初始翻转： 枚举区间长度，并计算单位根 逐个枚举区间（哪...

FFT代码上的实现细节 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132584208 ω\omegaω 的计算 ωn1\omega_n^1ωn1​ 的计算 考虑单位圆， ωn1\omega_n^1ωn1​ 为： 也就是： 注：op为判断当前为dft还是idft ωni\omega_n^iωni​ 的计算 当要计算 ωni\omega_n^iωni​ 时，只需要在 ωni−1\omega_n^{i-1}ωni−1​ 基础上乘 ωn1\omega_n^1...

傅里叶变换(FFT)笔记存档 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132582930 参考博客： https://www.luogu.com.cn/blog/command-block/fft-xue-xi-bi-ji 目录： FFT引入 复数相关知识 单位根及其相关性质 DFT过程（难点） DFT结论（重要） IDFT结论（重要） IDFT结论证明（难点） FFT引入 复数相关知识 单位根及其相关性质 DF...

dp答案和状态互换 || 多询问类dp转倍增/二分优化：CF1175E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132571504 https://www.luogu.com.cn/problem/CF1175E Trick 1 按照正常套路 dpidp_idpi​ 为到达 iii （限制）最少多少条（答案），其实可以转化为 dpidp_idpi​ 用 iii 条（限制）最远可以到达哪里（答案） 对于难以解决的dp，可以尝试把状态和答案互换，观察是否...

动态维护直径 || 动态维护树上路径 || 涉及LCA点转序列 || 对欧拉环游序用数据结构维护：1192B 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132566345 https://www.luogu.com.cn/problem/CF1192B 对于直径的求法，常用dp或两次dfs，但如果要动态维护似乎都不太方面，那么可以维护树上路径最大值。 树上路径为： depu+depv−2×deplca(u,v)dep_u+dep_v-2\times de...

后缀自动机SAM 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132560666 https://www.luogu.com.cn/problem/P3804 fail：当前区间-1（最短串 去掉最前面 的字符） nxt：任意串 加上最后面 考虑新加入的字符为x，上一个为p，则 nxt[p][x]=cnxt[p][x]=cnxt[p][x]=c 当前的每个后缀如果本身nxt为空，都可以加x 代码： 然后考虑现在这样： 如果整个区间可以直接...

cdq优化背包转移：GYM104531I 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132549832 https://codeforces.com/gym/104531/problem/I 转化部分： 关于 括号序列与问号 问题的一类处理方法 发现一个区间 [i:j][i:j][i:j] 合法要满足以下条件： 最后一个很好搞。前3个就是个cdq形式。 第一个拿来排序，后面对于黑白点分别以不同的形式（数）存在。 dp类cdq中，应先dp左，再计算左对...

二分队列+决策单调性优化dp：P6246 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132522515 https://www.luogu.com.cn/problem/P6246 决策单调性 若 dpidp_idpi​ 由 jjj 转移，则 dpi+1dp_{i+1}dpi+1​ 转移点 kkk 满足 k≥jk\ge jk≥j 发现决策点满足单调，但遍历的点不满足单调，不能用双指针，考虑二分队列。 二分队列 假设前 iii 个已定，只考虑从前转移到后...

wqs二分 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132522464 前提：答案满足凸性 题目类似为 nnn 个里面选 mmm 个求某种代价，暴力二维dp复杂度大，但容易计算不限制选的次数。 由于不限制选的次数，所以给选一个东西给一个代价 vvv ，然后判断最后选了多少个，再来调整这个 vvv 要方便调整这个 vvv ，就要二分。而能二分，说明具有单调性。把 vvv 视为斜率，斜率有单调性，所以原函数具有凸性。