zhangxixi的博客

分数问题善用移项：0902T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132647332 其实就是分数规划，但不完全是。 对于求 ∑pili∑li\Large\frac{\sum p_il_i}{\sum l_i}∑li​∑pi​li​​ 在限定条件下的最大值，此类问题可以考虑 二分答案 并 移项 。 ∑pili∑li≥k\Large\frac{\sum p_il_i}{\sum l_i}\ge k ∑li​∑pi​li​​≥k ∑pili≥k∑li...

图上简单路径问题——转化为圆方树问题：abc318_g 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132645934 https://atcoder.jp/contests/abc318/tasks/abc318_g 对原图建圆方树后，任意两点间的简单路径必然为其树上路径上方点对应其边双的点。 然后判断A，C路径上的方点是否会有B 圆方树： 12345678910111213141516void dfs(int x) { dfn[x]=low...

线性预处理整除分块 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132596085 有时候要求前 nnn 个： 暴力整除分块是 O(nn)O(n\sqrt n)O(nn​) 的，但可以线性预处理 首先我们让 iii 取遍 0 到正无穷，考虑差分。 思考 n−1n-1n−1 变成 nnn ，哪些 iii 会发生变化。只有 nnn 的因数，所以差分出来其实就是 nnn 的 因数个数 。这个可以线性筛 O(n)O(n)O(n) 预处理。 然后再做个前缀和就还原...

利用网络流通过拆点判断图的路径存在性问题：abc318_g 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132644032 https://atcoder.jp/contests/abc318/tasks/abc318_g 对于图上一类路径是否存在问题，可以考虑网络流。 Trick1 路径存在转网络流 题目转化为： 找出两条不交路径 B->A, B->C 对于已经找到的路径，我们 不能再走 。对于当前我们找到的某条路径，我们可能进行 反悔 ...

善用值域数据结构+操作离线：1864F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132631673 发现题目中有两个维度： 维护数值，发布计算某种情况下的答案 多个查询 两个维度，发现很难分开做。考虑对操作离线，同时维护两个维度的东西。 类似线段操作，左边入时±，右边出时-+ 本质是一种扫描线的思想

多项式求逆 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132612478 已知 FFF ，求 GGG 考虑倍增 F(x)∗H(x)≡1(modxn/2)F(x) * H(x) \equiv 1 \pmod{x^{n/2}}F(x)∗H(x)≡1(modxn/2) F(x)∗G(x)≡1(modxn/2)F(x) * G(x) \equiv 1 \pmod{x^{n/2}}F(x)∗G(x)≡1(modxn/2) 假设 HHH 已知，求G 做差可得： H...

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...