根号分治与多项式的巧妙结合：GYM-104386G
根号分治与多项式的巧妙结合：GYM-104386G
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132866002
使用范围：序列上对于 每种 数的计数问题
考虑对每种数的出现次数进行根号分治
如果出现次数很少，直接平方暴力即可
如果很大考虑任意 ，我们拆一下，再移一下，然后就变成了卷积形式
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-03
环上计数+计数转概率：ABC318EX
环上计数+计数转概率：ABC318EX 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132650494 https://atcoder.jp/contests/abc318/tasks/abc318_h 先转为概率， fif_ifi 表示 iii 个点两人都AC的概率， gig_igi 表示恰好一个人AC的概率。 两个人都AC，只能为全部自环， fi=1i!f_i=\frac 1 {i!} fi=i!1 现在求 gng_ngn 。然后有个定理， ...
2023-08-30
NTT总结
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 实现细节： ...
2026-06-18
容斥原理+哈夫曼式多项式乘法NTT：ABC462G
容斥原理+哈夫曼式多项式乘法NTT：ABC462G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162099398 https://atcoder.jp/contests/abc462/tasks/abc462_g 首先根据容斥原理，我们相当于求： 我们对颜色进行分类，对于颜色 kkk ，我们假设有 XkX_kXk 个球， YkY_kYk 个盒子。 我们现在枚举它有 DkD_kDk 个球放在相应颜色的盒子里，方案有： 因为颜色间不相互影响，所以这...
2023-09-18
简单的反射容斥与多项式快速幂：Loj#6738. 王的象棋世界
简单的反射容斥与多项式快速幂：Loj#6738. 王的象棋世界 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132978606 首先看到不能走出边界，发现是个反射容斥 对于此题，我们可以采用循环卷积来实现反射容斥 也就是说，如果我们走出了边界，相当于就是走到了另一边 而实现这个过程我们可以把卷完后 i+pi+pi+p 的部分直接平移到 iii 就行 加速这个过程可以用多项式快速幂 1234567891011121314151617181920212223...
2023-09-25
生成函数套sperner定理+哈夫曼树思想维护多个多项式乘法：CF1257G
生成函数套sperner定理+哈夫曼树思想维护多个多项式乘法：CF1257G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133270189 首先有spener定理，肯定选 m2\frac m 22m 最优 那怎么计算本质不同的选数方案呢？根据一些生成函数的知识，某个质数出现次数为 ccc ，我们就可以令其为 1+x+x2+⋯+xc1+x+x^2+\dots+x^c1+x+x2+⋯+xc ，然后所有多项式相乘的第 m2\frac m 22m 项即为答案...
2026-07-26
博弈论找性质mex用容斥+NTT优化：26暑杭电 2-05
博弈论找性质mex用容斥+NTT优化：26暑杭电 2-05 1005 减数游戏 2 博弈 先把博弈论的问题解决掉，怎样是最优的。 目的是让对手尽可能地吃掉有的数 我们来看一个数轴： 只要蓝色是先手： 奇数连续段时，它必然比绿色少吃1个 偶数段时，它和绿色相等 而且通过上面这种策略，它每次都可以占据空白段。 因此，关键在于谁能获得空白段的主动权 而空白段的主动权，只和第一个连续段的长度有关。 如果第一个连续段长度为偶数，那么先手就必胜了。 容斥 不妨令 mex(S)=p\text{mex}(S)=pmex(S)=p，在 1∼p−11\sim p-11∼p−1 内有 rrr 个空，...