三模数NTT模板
2024-09-02 22:16:36
求两个多项式的卷积对任意数p取模
两个好记的FNT模数:
5*2^25+1
7*2^26+1
原根都为3
//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Formylove return 0
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
const int N=,g=;
typedef long long LL;
typedef double db;
typedef long double LD;
using namespace std;
int n,m,mod;
LL a[][N],b[][N],p[]={,,},gi[]={,,};
LL ans[N]; template<typename T>void read(T &x) {
char ch=getchar(); x=; T f=;
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} LL ksc(LL a,LL b,LL p) {
LL tp=a*b-(LL)((LD)a/p*b+1.0e-8)*p;
return tp<?tp+p:tp%p;
} LL ksm(LL a,LL b,LL p) {
LL rs=,bs=a%p;
while(b) {
if(b&) rs=ksc(rs,bs,p);
bs=ksc(bs,bs,p);
b>>=;
}
return rs;
} int l,rev[N];
void FFT(int n,LL a[],int f,int p,int gi) {
For(i,,n-) if(i<rev[i]) swap(a[i],a[rev[i]]);
for(int i=;i<n;i<<=) {
LL wi=ksm((f==)?g:gi,(p-)/(i<<),p);
for(int j=,pp=(i<<);j<n;j+=pp) {
LL w=;
for(int k=;k<i;k++,w=w*wi%p) {
LL x=a[j+k],y=w*a[j+k+i]%p;
a[j+k]=(x+y)%p; a[j+k+i]=(x-y+p)%p;
}
}
}
if(f==-) {
LL inv=ksm(n,p-,p);
For(i,,n) a[i]=a[i]*inv%p;
}
} int main() {
#ifdef ANS
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
read(n); read(m); read(mod);
For(i,,n) { read(a[][i]); a[][i]=a[][i]=a[][i]; }
For(i,,m) { read(b[][i]); b[][i]=b[][i]=b[][i]; }
m+=n;
for(n=;n<=m;n<<=) l++;
For(i,,n) rev[i]=(rev[i>>]>>)|((i&)<<(l-));
For(i,,) {
FFT(n,a[i],,p[i],gi[i]);
FFT(n,b[i],,p[i],gi[i]);
For(j,,n) a[i][j]=a[i][j]*b[i][j]%p[i];
FFT(n,a[i],-,p[i],gi[i]);
}
LL p1=p[],p2=p[],p3=p[];
For(i,,m) {
LL b1=a[][i],b2=a[][i],b3=a[][i],b4;
b4=(ksc(ksc(b1,ksm(p2,p1-,p1),p1*p2),p2,p1*p2)+ksc(ksc(b2,ksm(p1,p2-,p2),p1*p2),p1,p1*p2))%(p1*p2);
LL k=((b3%p3-b4%p3+p3)%p3)*ksm(p1*p2,p3-,p3)%p3;
ans[i]=(b4%mod+k*p1%mod*p2%mod)%mod;
}
For(i,,m) printf("%lld ",ans[i]); puts("");
Formylove;
}
最新文章
- html5学习笔记4--API Range对象(一)
- 将Microsoft Ajax Minifier集成到VS2013对JS、CSS进行编译时压缩
- 网页FLASH幻灯片播放带链接源代码 pixviewer.swf使用(转)
- DP:Making the Grade(POJ 3666)
- CentOS 7 /RHEL 7: How To Change The System Locale
- Extjs随笔
- Qt版helloworld
- 从Kali 2.0 转至 Kali Rolling
- css三角形绘制
- IIS7 配置 PHP5.5
- 组态Log4j(非常具体的)
- 百度CSND博客在搜索栏中显示图片
- Android onTouchEvent方法
- 双层嵌套json字符串(即json对象内嵌json数组)解析为Map
- Spring Cloud微服务架构图
- Linux 驱动——Button驱动1
- python: 递归函数(科赫雪花)
- SpringMVC的启动
- platform总线,设备,驱动的注册
- 【刷题】BZOJ 3512 DZY Loves Math IV
热门文章
- selenium IDE的安装及录制回放的简单使用
- systemctl命令的使用及服务状态的查看
- 自然数幂和&;伯努利数(Bernoulli)
- shell脚本中:单引号和双引号的区别
- net core发邮件——MimeKit
- Java——Eclipse使用
- BZOJ 4517: [Sdoi2016]排列计数(组合数学)
- error C4996: &#39;strcpy&#39;: This function or variable may be unsafe. Consider using strcpy_s instead.【转载】
- idea从零搭建简单的springboot+Mybatis
- 剑指offer——03替换空格