加载中...

atcoder Convolution库（NTT）用法

发表于2026-06-18|OI（大学）高考复键语法

|总字数:162|阅读时长:1分钟|浏览量:

atcoder Convolution库（NTT）用法

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162096360

求：

$c_i = \sum_{j = 0}^i a_j b_{i - j}$

用法：

1	vector<T> convolution<int m = 998244353>(vector<T> a, vector<T> b)

其中 $T$ 是int、longlong等东西

也可以提前定义：

1 2	template <int m = 998244353, typename T> vector<T> convolution(vector<T> a, vector<T> b);

m必须满足NTT的相应要求

在这里插入图片描述

如果不取模的话，即在 long long 范围内

1	vector<ll> convolution_ll(vector<ll> a, vector<ll> b)

文章作者: zhangxixi

文章链接: http://zhangxixi2008.github.io/post/2d2acf4

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！

相关推荐

分治NTT/在线卷积

分治NTT/在线卷积本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132670095 https://www.luogu.com.cn/problem/P4721 已知 ggg ，求考虑分治，现在在 [l,r][l,r][l,r] ，先计算 [l,mid][l, mid][l,mid] ，然后计算 [l,mid][l, mid][l,mid] 对 [mid+1,r][mid+1,r][mid+1,r] 的贡献。计算左对右的贡献，就把左边的 fff ...

环上计数+计数转概率：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 。然后有个定理， ...

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 实现细节： ...

生成函数套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 项即为答案...

根号分治与多项式的巧妙结合：GYM-104386G

根号分治与多项式的巧妙结合：GYM-104386G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132866002 使用范围：序列上对于每种数的计数问题考虑对每种数的出现次数进行根号分治如果出现次数很少，直接平方暴力即可如果很大考虑任意 (i,j)(i,j)(i,j) ，我们拆一下，再移一下，然后就变成了卷积形式

容斥原理+哈夫曼式多项式乘法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 个球放在相应颜色的盒子里，方案有：因为颜色间不相互影响，所以这...

数据加载中