不想存本地,丢这里好了
#include<bits/stdc++.h>
typedef long long ll;
#define add(a,b) ((a+b<mod)?(a+b):(a+b-mod))
#define minus(a,b) ((a>=b)?(a-b):(a-b+mod))
#define Poly vector<ll>
using namespace std;
const int N=4e6+50;
const int g=3,mod=998244353,gi=332748118;
int qpow_num(int a,int b) {
int ans=1;
while(b) {
if(b&1) ans=1ll*ans*a%mod;
a=1ll*a*a%mod,b>>=1;
}
return ans;
}
int pow_inv(int x) {
return qpow_num(x,mod-2);
}
int powg[N],powgi[N],powinv[N];
void init() {
powinv[1]=1;
for(int i=2;i<=N-50;++i) powinv[i]=1ll*(mod-mod/i)*powinv[mod%i]%mod;
for(int i=1,j=0;i<=mod+1;i<<=1,++j) powg[j]=qpow_num(g,(mod-1)/i),powgi[j]=qpow_num(gi,(mod-1)/i);
}
Poly operator +(Poly a,Poly b) {
Poly ans;
ans.clear();
for(int i=0;i<min(a.size(),b.size());++i) ans.push_back(add(a[i],b[i]));
if(a.size()<b.size()) for(int i=a.size();i<b.size();++i) ans.push_back(b[i]);
else for(int i=b.size();i<a.size();++i) ans.push_back(a[i]);
return ans;
}
Poly operator -(Poly a,Poly b) {
Poly ans;
ans.clear();
for(int i=0;i<min(a.size(),b.size());++i) ans.push_back(minus(a[i],b[i]));
if(a.size()<b.size()) for(int i=a.size();i<b.size();++i) ans.push_back(minus(0,b[i]));
else for(int i=b.size();i<a.size();++i) ans.push_back(a[i]);
return ans;
}
Poly operator *(Poly a,int b) {
Poly ans;
ans.clear();
for(int i=0;i<a.size();++i) ans.push_back(a[i]*b%mod);
return ans;
}
Poly operator *(int a,Poly b) {
return b*a;
}
Poly operator /(Poly a,int b) {
Poly ans;
ans.clear();
for(int i=0;i<a.size();++i) ans.push_back(a[i]*pow_inv(b)%mod);
return ans;
}
int rev[N];
int w[N];
void ntt(Poly &a,int type) {
w[0]=1;
for(int i=0;i<a.size();++i) if(i<rev[i]) swap(a[i],a[rev[i]]);
for(int mid=1,tims=1;mid<a.size();mid<<=1,++tims) {
int g1=(type==1)?powg[tims]:powgi[tims];
for(int i=1;i<mid;++i) w[i]=1ll*w[i-1]*g1%mod;
for(int i=0;i<a.size();i+=mid<<1)
for(int j=0;j<mid;++j) {
int y=1ll*a[i+j+mid]*w[j]%mod;
a[i+j+mid]=minus(a[i+j],y),a[i+j]=add(a[i+j],y);
}
}
}
Poly operator *(Poly a,Poly b) {
Poly ans;
ans.clear();
int siza=a.size(),sizb=b.size(),siz=a.size()+b.size()-1,bit=0,tot=1;
while(tot<siz) tot<<=1,++bit;
for(int i=0;i<tot;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
a.resize(tot,0),b.resize(tot,0);
ntt(a,1),ntt(b,1);
for(int i=0;i<tot;++i) ans.push_back(a[i]*b[i]%mod);
ntt(ans,-1);
int intot=pow_inv(tot);
for(int i=0;i<tot;++i) ans[i]=ans[i]*intot%mod;
Poly lstans(ans.begin(),ans.begin()+siz);
return lstans;
}
Poly inv(Poly a,int realsiz=0) {
Poly ans;
ans.clear();
int siz=(realsiz)?realsiz:a.size();
int bit=0,tot=1;
while(tot<siz) tot<<=1,++bit;
a.resize(tot,0);
ans.push_back(pow_inv(a[0]));
for(int len=1;len<a.size();len<<=1) {
Poly tmp(a.begin(),a.begin()+(len<<1));
Poly anss;
anss.clear();
int sizz=tmp.size()+ans.size()*2-1,bitt=0,tott=1;
while(tott<sizz) tott<<=1,++bitt;
for(int i=0;i<tott;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bitt-1));
tmp.resize(tott,0),ans.resize(tott,0);
ntt(tmp,1),ntt(ans,1);
for(int i=0;i<tott;++i) anss.push_back(minus(2ll*ans[i]%mod,1ll*tmp[i]*ans[i]%mod*ans[i]%mod));
ntt(anss,-1);
int intot=pow_inv(tott);
for(int i=0;i<tott;++i) anss[i]=anss[i]*intot%mod;
ans.clear();
for(int i=0;i<(len<<1);++i) ans.push_back(anss[i]);
}
Poly lstans(ans.begin(),ans.begin()+siz);
return lstans;
}
Poly operator /(Poly a,Poly b) {
Poly ans;
ans.clear();
int siz=a.size()-b.size()+1;
reverse(a.begin(),a.end()),reverse(b.begin(),b.end());
ans=a*inv(b,siz);
Poly lstans(ans.begin(),ans.begin()+siz);
reverse(lstans.begin(),lstans.end());
return lstans;
}
Poly operator %(Poly a,Poly b) {
Poly ans;
ans.clear();
ans=a-a/b*b;
Poly lstans(ans.begin(),ans.begin()+b.size()-1);
return lstans;
}
Poly deriv(Poly a) {
Poly ans;
ans.clear();
for(int i=1;i<a.size();++i) ans.push_back(a[i]*i%mod);
return ans;
}
Poly integ(Poly a) {
Poly ans;
ans.clear();
ans.push_back(0);
for(int i=0;i<a.size();++i) ans.push_back(a[i]*powinv[i+1]%mod);
return ans;
}
Poly ln(Poly a,int realsiz=0) {
Poly ans;
int siz=(realsiz)?realsiz:a.size();
ans.clear();
ans=integ(deriv(a)*inv(a,siz));
Poly lstans(ans.begin(),ans.begin()+siz);
return lstans;
}
Poly Exp(Poly a) {
Poly ans;
ans.clear();
int siz=a.size(),bit=0,tot=1;
while(tot<siz) tot<<=1,++bit;
a.resize(tot,0);
ans.push_back(1);
for(int len=1;len<a.size();len<<=1) {
Poly tmp(a.begin(),a.begin()+(len<<1));
Poly tmpp;
tmpp.clear();
tmpp.push_back(1);
tmpp=ans*(tmpp-ln(ans,(len<<1))+tmp);
ans.clear();
for(int i=0;i<(len<<1);++i) ans.push_back(tmpp[i]);
}
Poly lstans(ans.begin(),ans.begin()+siz);
return lstans;
}
Poly qpow_poly(Poly a,int b,int realsiz=0) {
Poly ans;
int siz=(realsiz)?realsiz:a.size();
ans=Exp(b*ln(a));
Poly lstans(ans.begin(),ans.begin()+siz);
return lstans;
}
Poly sqrt(Poly a,int realsiz=0) {
Poly ans;
int siz=(realsiz)?realsiz:a.size();
int bit=0,tot=1;
while(tot<siz) tot<<=1,++bit;
a.resize(tot,0);
ans.push_back(1);
for(int len=1;len<a.size();len<<=1) {
Poly tmp(a.begin(),a.begin()+(len<<1));
Poly tmpp;
tmpp.clear();
tmpp=(ans*ans+tmp)*inv(2*ans,len<<1);
ans.clear();
for(int i=0;i<(len<<1);++i) ans.push_back(tmpp[i]);
}
Poly lstans(ans.begin(),ans.begin()+siz);
return lstans;
}
int main() {
init();
return 0;
}
大佬,这都是啥呀?
多项式(