@[Simpson561](/space/show?uid=53034) NTT里面bit没用啊，还有就是为什么那么多1<<mid,1<<(mid+1)，写的不难受吗qwq。关于tmp完全可以预处理出来而不是每次算一下啊。Mul里面长度是$Len_F+Len_G-1$（这个没多大影响）。
by ecnerwaIa @ 2019-05-23 08:21:53
@[Simpson561](/space/show?uid=53034) 第129行改成从$Len_F-Len_G+1$开始。
by ecnerwaIa @ 2019-05-23 08:27:57
@[Simpson561](/space/show?uid=53034) 还有就是最后一个Mul，F,G后半部分没有全部清空
by ecnerwaIa @ 2019-05-23 08:46:15
@[Simpson561](/space/show?uid=53034) ```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=998244353,g=3;
const int MAXLEN=1<<23|1;
int N,M,F[MAXLEN],G[MAXLEN],ans[MAXLEN];//basic
int lim=1,lg=0,tmp[109],rev[MAXLEN];//NTT
int C[MAXLEN];//Inv
int Gr[MAXLEN],_Gr[MAXLEN],Q[MAXLEN],R[MAXLEN];//Devide
namespace IO
{
const int BUF_SIZE=1<<15;
char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
char *p_in_buf=in_buf+BUF_SIZE;
char *p_out_buf=out_buf;
inline char get_char()
{
if(p_in_buf==in_buf+BUF_SIZE) fread(in_buf,1,BUF_SIZE,stdin),p_in_buf=in_buf;
return *(p_in_buf++);
}
inline void put_char(char x)
{
if(p_out_buf==out_buf+BUF_SIZE) fwrite(out_buf,1,BUF_SIZE,stdout),p_out_buf=out_buf;
*(p_out_buf++)=x;
}
inline void flush()
{
if(p_out_buf!=out_buf) fwrite(out_buf,1,p_out_buf-out_buf,stdout),p_out_buf=out_buf;
}
// #define getchar() IO::get_char()
// #define putchar(x) IO::put_char(x)
inline int getint()
{
int x=0;
char c=getchar();
while(c<=32) c=getchar();
while(c>32) x=x*10+(c&15),c=getchar();
return x;
}
inline int getint(char &c)
{
int x=0;
c=getchar();
while(c<=32) c=getchar();
while(c>32) x=x*10+(c&15),c=getchar();
return x;
}
template <class T>
inline void _putint(T x)
{
return x?_putint(x/10), putchar((x%10)|48),void():void();
}
template <class T>
inline void putint(T x)
{
return x==0?putchar('0'),void():_putint(x),void();
}
inline void getline(char *s)
{
char c=getchar();
while(c=='\n') c=getchar();
while(c!='\n') *(s++)=c,c=getchar();
*s=0;
}
}
using namespace IO;
inline void _swap(int &a,int &b)
{
int _=a;
a=b,b=_;
}
inline int quickpower(int a,int n,int m)
{
int i,s;
for(i=a,s=1;n;n>>=1,i=i*i%m)
if(n&1) s=s*i%m;
return s;
}
inline void init(int len_sum)
{
lim=1,lg=0;
while(lim<=len_sum) lim<<=1,lg++;
for(register int i=1;i<=lim;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
for(register int mid=0;(1<<mid)<lim;mid++) tmp[mid]=quickpower(g,(MOD-1)>>(mid+1),MOD);
}
inline void NTT(int *F,const int len,const int inv_flg)
{
register int i,j,step,s,enk,wn,x,now,inv=quickpower(len,MOD-2,MOD);
for(i=0;i<len;i++) if(i<rev[i]) _swap(F[i],F[rev[i]]);
for(step=1,s=2,now=0;step<len;step<<=1,s<<=1,++now){
enk=tmp[now];
for(i=0;i<len;i+=s){
wn=1;
for(j=i;j<i+step;++j){
x=F[j+step]*wn%MOD;
F[j+step]=(F[j]-x+MOD)%MOD;
F[j]=(F[j]+x)%MOD;
wn=wn*enk%MOD;
}
}
}
if(inv_flg==-1)
{
reverse(F+1,F+len);
for(int i=0;i<len;i++) F[i]=F[i]*inv%MOD;
}
}
inline void Mul(int len_F,int len_G,int *F,int *G,int *Ans)
{
init(len_F+len_G-1);
memset(F+(lim>>1),0,lim<<2);
memset(G+(lim>>1),0,lim<<2);
NTT(F,lim,1),NTT(G,lim,1);
for(register int i=0;i<lim;i++) Ans[i]=F[i]*G[i]%MOD;
NTT(Ans,lim,-1);
}
inline void Inv(int len,int *F,int *Ans)
{
if(len==1) {Ans[0]=quickpower(F[0],MOD-2,MOD); return;}
Inv((len+1)>>1,F,Ans);
for(register int i=0;i<len;i++) C[i]=F[i];
for(register int i=len;i<lim;i++) C[i]=0;
init(len<<1);
NTT(C,lim,1),NTT(Ans,lim,1);
for(register int i=0;i<lim;i++) Ans[i]=(2-C[i]*Ans[i]%MOD+MOD)%MOD*Ans[i]%MOD;
NTT(Ans,lim,-1);
for(register int i=len;i<lim;i++) Ans[i]=0;
}
inline void Divide(int len_F,int len_G,int *F,int *G,int *Q,int *R)
{
for(register int i=0;i<=len_F;i++) Q[len_F-i]=F[i];
for(register int i=0;i<=len_G;i++) Gr[len_G-i]=G[i];
for(register int i=len_F-len_G+1;i<=len_G;i++) Gr[i]=0;
Inv(len_F-len_G+1,Gr,_Gr);
for(register int i=0;i<=len_F-len_G;i++) Gr[i]=_Gr[i];
Mul(len_F-len_G+1,len_F-len_G+1,Q,Gr,Q);
reverse(Q,Q+len_F-len_G+1);
for(register int i=len_F-len_G+1;i<=len_F;i++) Q[i]=0;
Mul(len_F-len_G+1,len_G+1,Q,G,R);
for(register int i=0;i<=len_G-1;i++) R[i]=(F[i]-R[i]+MOD)%MOD;
NTT(Q,lim,-1);
}
signed main()
{
N=getint(),M=getint();
for(int i=0;i<=N;i++) F[i]=getint();
for(int i=0;i<=M;i++) G[i]=getint();
Divide(N,M,F,G,Q,R);
for(int i=0;i<=N-M;i++) putint(Q[i]),putchar(' ');
putchar('\n');
for(int i=0;i<=M-1;i++) putint(R[i]),putchar(' ');
flush();
return 0;
}
```
这是修改完的兄弟，累死我了。
by ecnerwaIa @ 2019-05-23 08:49:37
@[Simpson561](/space/show?uid=53034)
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=998244353,g=3;
const int MAXLEN=1<<23|1;
int N,M,F[MAXLEN],G[MAXLEN],ans[MAXLEN];//basic
int lim=1,lg=0,tmp[109],rev[MAXLEN];//NTT
int C[MAXLEN];//Inv
int Gr[MAXLEN],_Gr[MAXLEN],Q[MAXLEN],R[MAXLEN];//Devide
namespace IO
{
const int BUF_SIZE=1<<15;
char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
char *p_in_buf=in_buf+BUF_SIZE;
char *p_out_buf=out_buf;
inline char get_char()
{
if(p_in_buf==in_buf+BUF_SIZE) fread(in_buf,1,BUF_SIZE,stdin),p_in_buf=in_buf;
return *(p_in_buf++);
}
inline void put_char(char x)
{
if(p_out_buf==out_buf+BUF_SIZE) fwrite(out_buf,1,BUF_SIZE,stdout),p_out_buf=out_buf;
*(p_out_buf++)=x;
}
inline void flush()
{
if(p_out_buf!=out_buf) fwrite(out_buf,1,p_out_buf-out_buf,stdout),p_out_buf=out_buf;
}
// #define getchar() IO::get_char()
// #define putchar(x) IO::put_char(x)
inline int getint()
{
int x=0;
char c=getchar();
while(c<=32) c=getchar();
while(c>32) x=x*10+(c&15),c=getchar();
return x;
}
inline int getint(char &c)
{
int x=0;
c=getchar();
while(c<=32) c=getchar();
while(c>32) x=x*10+(c&15),c=getchar();
return x;
}
template <class T>
inline void _putint(T x)
{
return x?_putint(x/10), putchar((x%10)|48),void():void();
}
template <class T>
inline void putint(T x)
{
return x==0?putchar('0'),void():_putint(x),void();
}
inline void getline(char *s)
{
char c=getchar();
while(c=='\n') c=getchar();
while(c!='\n') *(s++)=c,c=getchar();
*s=0;
}
}
using namespace IO;
inline void _swap(int &a,int &b)
{
int _=a;
a=b,b=_;
}
inline int quickpower(int a,int n,int m)
{
int i,s;
for(i=a,s=1;n;n>>=1,i=i*i%m)
if(n&1) s=s*i%m;
return s;
}
inline void init(int len_sum)
{
lim=1,lg=0;
while(lim<=len_sum) lim<<=1,lg++;
for(register int i=1;i<=lim;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
for(register int mid=0;(1<<mid)<lim;mid++) tmp[mid]=quickpower(g,(MOD-1)>>(mid+1),MOD);
}
inline void NTT(int *F,const int len,const int inv_flg)
{
register int i,j,step,s,enk,wn,x,now,inv=quickpower(len,MOD-2,MOD);
for(i=0;i<len;i++) if(i<rev[i]) _swap(F[i],F[rev[i]]);
for(step=1,s=2,now=0;step<len;step<<=1,s<<=1,++now){
enk=tmp[now];
for(i=0;i<len;i+=s){
wn=1;
for(j=i;j<i+step;++j){
x=F[j+step]*wn%MOD;
F[j+step]=(F[j]-x+MOD)%MOD;
F[j]=(F[j]+x)%MOD;
wn=wn*enk%MOD;
}
}
}
if(inv_flg==-1)
{
reverse(F+1,F+len);
for(int i=0;i<len;i++) F[i]=F[i]*inv%MOD;
}
}
inline void Mul(int len_F,int len_G,int *F,int *G,int *Ans)
{
init(len_F+len_G-1);
memset(F+(lim>>1),0,lim<<2);
memset(G+(lim>>1),0,lim<<2);
NTT(F,lim,1),NTT(G,lim,1);
for(register int i=0;i<lim;i++) Ans[i]=F[i]*G[i]%MOD;
NTT(Ans,lim,-1);
}
inline void Inv(int len,int *F,int *Ans)
{
if(len==1) {Ans[0]=quickpower(F[0],MOD-2,MOD); return;}
Inv((len+1)>>1,F,Ans);
for(register int i=0;i<len;i++) C[i]=F[i];
for(register int i=len;i<lim;i++) C[i]=0;
init(len<<1);
NTT(C,lim,1),NTT(Ans,lim,1);
for(register int i=0;i<lim;i++) Ans[i]=(2-C[i]*Ans[i]%MOD+MOD)%MOD*Ans[i]%MOD;
NTT(Ans,lim,-1);
for(register int i=len;i<lim;i++) Ans[i]=0;
}
inline void Divide(int len_F,int len_G,int *F,int *G,int *Q,int *R)
{
for(register int i=0;i<=len_F;i++) Q[len_F-i]=F[i];
for(register int i=0;i<=len_G;i++) Gr[len_G-i]=G[i];
for(register int i=len_F-len_G+1;i<=len_G;i++) Gr[i]=0;
Inv(len_F-len_G+1,Gr,_Gr);
for(register int i=0;i<=len_F-len_G;i++) Gr[i]=_Gr[i];
Mul(len_F-len_G+1,len_F-len_G+1,Q,Gr,Q);
reverse(Q,Q+len_F-len_G+1);
for(register int i=len_F-len_G+1;i<=len_F;i++) Q[i]=0;
Mul(len_F-len_G+1,len_G+1,Q,G,R);
for(register int i=0;i<=len_G-1;i++) R[i]=(F[i]-R[i]+MOD)%MOD;
NTT(Q,lim,-1);
}
signed main()
{
N=getint(),M=getint();
for(int i=0;i<=N;i++) F[i]=getint();
for(int i=0;i<=M;i++) G[i]=getint();
Divide(N,M,F,G,Q,R);
for(int i=0;i<=N-M;i++) putint(Q[i]),putchar(' ');
putchar('\n');
for(int i=0;i<=M-1;i++) putint(R[i]),putchar(' ');
flush();
return 0;
}
```
by ecnerwaIa @ 2019-05-23 08:49:54
@[Simpson561](/space/show?uid=53034) 哦，有个地方写错了qwq
by ecnerwaIa @ 2019-05-23 08:51:33
@[Simpson561](/space/show?uid=53034)
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=998244353,g=3;
const int MAXLEN=1<<23|1;
int N,M,F[MAXLEN],G[MAXLEN],ans[MAXLEN];//basic
int lim=1,lg=0,tmp[109],rev[MAXLEN];//NTT
int C[MAXLEN];//Inv
int Gr[MAXLEN],_Gr[MAXLEN],Q[MAXLEN],R[MAXLEN];//Devide
namespace IO
{
const int BUF_SIZE=1<<15;
char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
char *p_in_buf=in_buf+BUF_SIZE;
char *p_out_buf=out_buf;
inline char get_char()
{
if(p_in_buf==in_buf+BUF_SIZE) fread(in_buf,1,BUF_SIZE,stdin),p_in_buf=in_buf;
return *(p_in_buf++);
}
inline void put_char(char x)
{
if(p_out_buf==out_buf+BUF_SIZE) fwrite(out_buf,1,BUF_SIZE,stdout),p_out_buf=out_buf;
*(p_out_buf++)=x;
}
inline void flush()
{
if(p_out_buf!=out_buf) fwrite(out_buf,1,p_out_buf-out_buf,stdout),p_out_buf=out_buf;
}
// #define getchar() IO::get_char()
// #define putchar(x) IO::put_char(x)
inline int getint()
{
int x=0;
char c=getchar();
while(c<=32) c=getchar();
while(c>32) x=x*10+(c&15),c=getchar();
return x;
}
inline int getint(char &c)
{
int x=0;
c=getchar();
while(c<=32) c=getchar();
while(c>32) x=x*10+(c&15),c=getchar();
return x;
}
template <class T>
inline void _putint(T x)
{
return x?_putint(x/10), putchar((x%10)|48),void():void();
}
template <class T>
inline void putint(T x)
{
return x==0?putchar('0'),void():_putint(x),void();
}
inline void getline(char *s)
{
char c=getchar();
while(c=='\n') c=getchar();
while(c!='\n') *(s++)=c,c=getchar();
*s=0;
}
}
using namespace IO;
inline void _swap(int &a,int &b)
{
int _=a;
a=b,b=_;
}
inline int quickpower(int a,int n,int m)
{
int i,s;
for(i=a,s=1;n;n>>=1,i=i*i%m)
if(n&1) s=s*i%m;
return s;
}
inline void init(int len_sum)
{
lim=1,lg=0;
while(lim<=len_sum) lim<<=1,lg++;
for(register int i=1;i<=lim;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
for(register int mid=0;(1<<mid)<lim;mid++) tmp[mid]=quickpower(g,(MOD-1)>>(mid+1),MOD);
}
inline void NTT(int *F,const int len,const int inv_flg)
{
register int i,j,step,s,enk,wn,x,now,inv=quickpower(len,MOD-2,MOD);
for(i=0;i<len;i++) if(i<rev[i]) _swap(F[i],F[rev[i]]);
for(step=1,s=2,now=0;step<len;step<<=1,s<<=1,++now){
enk=tmp[now];
for(i=0;i<len;i+=s){
wn=1;
for(j=i;j<i+step;++j){
x=F[j+step]*wn%MOD;
F[j+step]=(F[j]-x+MOD)%MOD;
F[j]=(F[j]+x)%MOD;
wn=wn*enk%MOD;
}
}
}
if(inv_flg==-1)
{
reverse(F+1,F+len);
for(int i=0;i<len;i++) F[i]=F[i]*inv%MOD;
}
}
inline void Mul(int len_F,int len_G,int *F,int *G,int *Ans)
{
init(len_F+len_G-1);
memset(F+len_F,0,(lim-len_F)<<3);
memset(G+len_G,0,(lim-len_G)<<3);
NTT(F,lim,1),NTT(G,lim,1);
for(register int i=0;i<lim;i++) Ans[i]=F[i]*G[i]%MOD;
NTT(Ans,lim,-1);
}
inline void Inv(int len,int *F,int *Ans)
{
if(len==1) {Ans[0]=quickpower(F[0],MOD-2,MOD); return;}
Inv((len+1)>>1,F,Ans);
for(register int i=0;i<len;i++) C[i]=F[i];
for(register int i=len;i<lim;i++) C[i]=0;
init(len<<1);
NTT(C,lim,1),NTT(Ans,lim,1);
for(register int i=0;i<lim;i++) Ans[i]=(2-C[i]*Ans[i]%MOD+MOD)%MOD*Ans[i]%MOD;
NTT(Ans,lim,-1);
for(register int i=len;i<lim;i++) Ans[i]=0;
}
inline void Divide(int len_F,int len_G,int *F,int *G,int *Q,int *R)
{
for(register int i=0;i<=len_F;i++) Q[len_F-i]=F[i];
for(register int i=0;i<=len_G;i++) Gr[len_G-i]=G[i];
for(register int i=len_F-len_G+1;i<=len_G;i++) Gr[i]=0;
Inv(len_F-len_G+1,Gr,_Gr);
for(register int i=0;i<=len_F-len_G;i++) Gr[i]=_Gr[i];
Mul(len_F-len_G+1,len_F-len_G+1,Q,Gr,Q);
reverse(Q,Q+len_F-len_G+1);
for(register int i=len_F-len_G+1;i<=len_F;i++) Q[i]=0;
for(int i=0;i<=len_F-len_G;++i)putint(Q[i]),putchar(' ');
putchar('\n');
Mul(len_F-len_G+1,len_G+1,Q,G,R);
for(register int i=0;i<=len_G-1;i++) R[i]=(F[i]-R[i]+MOD)%MOD;
}
signed main()
{
// freopen("0.in","r",stdin);
N=getint(),M=getint();
for(int i=0;i<=N;i++) F[i]=getint();
for(int i=0;i<=M;i++) G[i]=getint();
Divide(N,M,F,G,Q,R);
for(int i=0;i<=M-1;i++) putint(R[i]),putchar(' ');
flush();
return 0;
}
```
通过代码。不懂的地方可以来问我
by ecnerwaIa @ 2019-05-23 09:00:47
@[千年之狐_天才](/space/show?uid=54113) 谢谢大佬%%%
by Simpson561 @ 2019-05-23 12:15:44