社区讨论
为什么这个代码在编译器里不能输入直接结束而能洛谷 AC呢
P3803【模板】多项式乘法(FFT)参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo81hhae
- 此快照首次捕获于
- 2023/10/27 11:14 2 年前
- 此快照最后确认于
- 2023/10/27 11:14 2 年前
rt,NTT
NTT 函数写法可能有点怪,但是经过测试这部分没有问题。(直接在主函数中进行不同多项式表示方法转换无异常)
我想将多项式乘法部分写成一个独立的函数,然而加上这个函数之后,点击运行,不能输入程序就结束了,但是交到洛谷 FFT 模板题上却能 AC,这是为什么呢?
是这个独立的计算多项式乘法的函数
poly_mul() 哪里错了呢,还是编译器的问题呢?tips:编译器使用 dev
求大佬解答/kel/kel
代码:
CPP#include"iostream"
#include"cstdio"
#include"cmath"
using namespace std;
#define MAXN 1000005
#define MOD 998244353
#define ll long long
int N,M,n=1,l=0;
struct poly
{
int a[MAXN*3];
}f,g;
int res[MAXN*3],w[MAXN*3];
int mul(int a,int b){return (ll)a*b%MOD;}
int quickpow(int a,int b)
{
int ans=1,base=a;
while(b)
{
if(b&1) ans=mul(ans,base);
base=mul(base,base);
b>>=1;
}
return ans;
}
int inv(int a){return quickpow(a,MOD-2);}
void NTT(int *a,int unit)
{
w[0]=1,w[1]=quickpow(unit,(MOD-1)/n);
for(int i=2;i<n;i++) w[i]=w[i]=mul(w[1],w[i-1]);
for(int i=0;i<n;i++) if(i<res[i]) swap(a[i],a[res[i]]);
for(int i=2;i<=l+1;i++)
{
int t=n>>(i-1);
for(int j=1;j<=t;j++)
{
int s=n/t;
for(int k=0;k<(s>>1);k++)
{
int op=s*(j-1)+k,G=mul(a[op+(s>>1)],w[k*t]);
a[op+(s>>1)]=(a[op]-G+MOD)%MOD;
a[op]=(a[op]+G)%MOD;
}
}
}
}
poly poly_mul(int a[],int b[],int n)
{
poly h;
NTT(a,3),NTT(b,3);
for(int i=0;i<n;i++) a[i]=mul(a[i],b[i]);
NTT(a,inv(3));
int m=inv(n);
for(int i=0;i<n;i++) h.a[i]=mul(a[i],m);
return h;
}
int main()
{
scanf("%d%d",&N,&M);
while(n<=N+M) n<<=1,l++;
for(int i=0;i<=N;i++) scanf("%d",&f.a[i]);
for(int i=0;i<=M;i++) scanf("%d",&g.a[i]);
for(int i=0;i<n;i++) res[i]=(res[i>>1]>>1)|((i&1)<<(l-1));
poly H=poly_mul(f.a,g.a,n);
for(int i=0;i<=N+M;i++) printf("%d ",H.a[i]);
return puts(""),0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...