社区讨论

为什么这个代码在编译器里不能输入直接结束而能洛谷 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 条回复,欢迎继续交流。

正在加载回复...