根号分治与多项式的巧妙结合：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-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-25
矩阵+NTT生成函数优化dp：2026暑杭电 2-02 表达式 2
矩阵+NTT生成函数优化dp：2026暑杭电 2-02 表达式 2 1002 表达式 2 dp 设 fi,kf_{i,k}fi,k 表示前 iii 个数字插入 kkk 个乘号的答案 gi,kg_{i,k}gi,k 表示前 iii 个数字，插入 kkk 个乘号，除了最后一段，前面每项的答案。 我们可以列出状态转移方程： fi,k=fi−1,k×10+si⋅gi,k（添加乘号）+fi−1,k−1⋅si（不添加乘号）f_{i,k} = f_{i-1,k} \times 10 + s_i \cdot g_{i,k}\text{（添加乘号）}+f_{i-1,k-1}\cdot s_i\tex...
2026-09-11
根号分治 + NTT优化dp转移：ICPC2026网络赛B
根号分治 + NTT优化dp转移：ICPC2026网络赛B 考虑一个朴素的dp 定义 cic_ici 表示有多少个 aaa 小于等于 iii。显然 iii 只有模这 cic_ici 个数才会改变。 设 fif_ifi 表示在整个过程中，有多少种排列使得 iii 存在过。显然对于 i<a1i<a_1i<a1，fif_ifi 就是答案。而 i≥a1i\ge a_1i≥a1，答案是0。 fi×1ci→j∈{a}fi mod jf_i\times \frac 1{c_i}\to_{j\in \{a\}}f_{i\,\bmod\, j} fi×ci1→j∈...
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 实现细节： ...
2023-08-31
多项式求逆
多项式求逆 本文搬运自本人高中时期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...