#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;
const int maxn=(1<<22)+5;
const int sqrtn=sqrt(maxn)+5;
const int inf=0x3f3f3f3f;
namespace poly {
// /*
const int mod=998244353;
const int g=3;
struct mint {
int val;
mint():val(0) {}
mint(ll tval) {
if(-mod<=tval&&tval<2*mod) {
if(tval>=mod) {
tval-=mod;
}
if(tval<0) {
tval+=mod;
}
} else {
tval%=mod;
if(tval<0) {
tval+=mod;
}
}
val=tval;
}
mint& operator += (const mint &b) {
val=val+b.val>=mod?val+b.val-mod:val+b.val;
return *this;
}
mint& operator -= (const mint &b) {
val=val-b.val<0?val-b.val+mod:val-b.val;
return *this;
}
mint& operator *= (const mint &b) {
val=1ll*val*b.val>=mod?1ll*val*b.val%mod:val*b.val;
return *this;
}
mint& operator /= (const mint &b) {
*this*=b.inv();
return *this;
}
friend mint operator + (const mint &a,const mint &b) {
mint ans=a;
ans+=b;
return ans;
}
friend mint operator - (const mint &a,const mint &b) {
mint ans=a;
ans-=b;
return ans;
}
friend mint operator * (const mint &a,const mint &b) {
mint ans=a;
ans*=b;
return ans;
}
friend mint operator / (const mint &a,const mint &b) {
mint ans=a;
ans/=b;
return ans;
}
friend bool operator < (const mint &a,const mint &b) {
return a.val<b.val;
}
friend bool operator > (const mint &a,const mint &b) {
return a.val>b.val;
}
friend bool operator == (const mint &a,const mint &b) {
return a.val==b.val;
}
friend bool operator != (const mint &a,const mint &b) {
return a.val!=b.val;
}
friend istream& operator >> (istream &is,mint &x) {
ll val;
cin>>val;
x.val=val%mod;
return is;
}
friend ostream& operator << (ostream &os,const mint &x) {
os<<x.val;
return os;
}
mint qpow(ll y) const {
mint x=*this,ans=1;
while(y) {
if(y&1) {
ans*=x;
}
x*=x;
y>>=1;
}
return ans;
}
mint inv() const {
// mod must be a prime
return qpow(mod-2);
}
mint sqrt() {
mint a=*this;
auto check=[&](mint x) {
return x.qpow((mod-1)/2)==1;
};
static mt19937 rnd(73385);
mint b=rnd()%mod;
while(check(b*b-a)) {
b=rnd()%mod;
}
static mint val=b*b-a;
struct Complex {
mint real,imag;
Complex(mint treal=0,mint timag=0):real(treal),imag(timag) {}
Complex operator * (const Complex &rhs) {
return {real*rhs.real+imag*rhs.imag*val,real*rhs.imag+imag*rhs.real};
}
Complex& operator *= (const Complex &rhs) {
return *this=*this*rhs;
}
};
auto qpow=[&](Complex x,int y) {
Complex ans={1};
while(y) {
if(y&1) {
ans*=x;
}
x*=x;
y>>=1;
}
return ans;
};
mint ans=qpow({b,1},(mod+1)/2).real;
return min(ans,mod-ans);
}
};
struct Pow {
const int B=4e4;
mint p1[maxn];
mint p2[maxn];
mint pow(int y) {
return p1[y%B]*p2[y/B];
}
void prepare(mint p) {
p1[0]=1;
for(int i=1;i<=B;i++) {
p1[i]=p*p1[i-1];
}
mint ans=1;
for(int i=1;i<=B;i++) {
ans*=p;
}
p2[0]=1,p2[1]=ans;
for(int i=2;i<=B;i++) {
p2[i]=p2[i-1]*ans;
}
}
} pw;
using Poly=vector<mint>;
int t[maxn];
bool inited=false;
Poly s[sqrtn];
Poly l[sqrtn];
mint w[maxn][2];
mint fact[maxn];
mint invf[maxn];
map<pii,Poly> mp;
void init() {
inited=true;
for(int i=1;i<maxn;i*=2) {
w[i][0]=mint(g).qpow((mod-1)/i);
w[i][1]=w[i][0].inv();
}
}
int extend(int x) {
int len=1;
while(len<x) {
len*=2;
}
return len;
}
void NTT(Poly &f,int op) {
int len=f.size();
for(int i=0;i<len;i++) {
t[i]=t[i>>1]>>1;
if(i&1) {
t[i]|=len>>1;
}
}
for(int i=0;i<len;i++) {
if(t[i]<i) {
swap(f[t[i]],f[i]);
}
}
for(int n=2;n<=len;n*=2) {
mint p=w[n][op];
for(int dt=0;dt<len;dt+=n) {
mint cur=1;
for(int i=0;i<n/2;i++) {
mint t=cur*f[i+n/2+dt];
f[i+n/2+dt]=f[i+dt]-t;
f[i+dt]=f[i+dt]+t;
cur*=p;
}
}
}
}
void DFT(Poly &f) {
NTT(f,0);
}
void IDFT(Poly &f) {
NTT(f,1);
int len=f.size();
mint invlen=mint(len).inv();
for(mint &x:f) {
x*=invlen;
}
}
Poly mul(Poly a,Poly b,int p=-1) {
assert(inited);
int n=a.size(),m=b.size(),len=extend(n+m-1);
if(p==-1) {
p=n+m-1;
}
if(n<=100||m<=100) {
Poly ans(n+m-1);
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
ans[i+j]+=a[i]*b[j];
}
}
ans.resize(p);
return ans;
}
a.resize(len);
b.resize(len);
DFT(a),DFT(b);
for(int i=0;i<len;i++) {
a[i]*=b[i];
}
IDFT(a);
a.resize(p);
return a;
}
// */
/*
int mod;
const double pi=acos(-1);
struct mint {
static int mod;
int val;
mint():val(0) {}
mint(ll tval) {
assert(mod);
if(-mod<=tval&&tval<2*mod) {
if(tval>=mod) {
tval-=mod;
}
if(tval<0) {
tval+=mod;
}
} else {
tval%=mod;
if(tval<0) {
tval+=mod;
}
}
val=tval;
}
mint& operator += (const mint &b) {
val=val+b.val>=mod?val+b.val-mod:val+b.val;
return *this;
}
mint& operator -= (const mint &b) {
val=val-b.val<0?val-b.val+mod:val-b.val;
return *this;
}
mint& operator *= (const mint &b) {
val=1ll*val*b.val>=mod?1ll*val*b.val%mod:val*b.val;
return *this;
}
mint& operator /= (const mint &b) {
*this*=b.inv();
return *this;
}
friend mint operator + (const mint &a,const mint &b) {
mint ans=a;
ans+=b;
return ans;
}
friend mint operator - (const mint &a,const mint &b) {
mint ans=a;
ans-=b;
return ans;
}
friend mint operator * (const mint &a,const mint &b) {
mint ans=a;
ans*=b;
return ans;
}
friend mint operator / (const mint &a,const mint &b) {
mint ans=a;
ans/=b;
return ans;
}
friend bool operator < (const mint &a,const mint &b) {
return a.val<b.val;
}
friend bool operator > (const mint &a,const mint &b) {
return a.val>b.val;
}
friend bool operator == (const mint &a,const mint &b) {
return a.val==b.val;
}
friend bool operator != (const mint &a,const mint &b) {
return a.val!=b.val;
}
friend istream& operator >> (istream &is,mint &x) {
ll val;
cin>>val;
x.val=val%mod;
return is;
}
friend ostream& operator << (ostream &os,const mint &x) {
os<<x.val;
return os;
}
mint qpow(ll y) const {
mint x=*this,ans=1;
while(y) {
if(y&1) {
ans*=x;
}
x*=x;
y>>=1;
}
return ans;
}
mint inv() const {
// mod must be a prime
return qpow(mod-2);
}
mint sqrt() {
mint a=*this;
auto check=[&](mint x) {
return x.qpow((mod-1)/2)==1;
};
static mt19937 rnd(73385);
mint b=rnd()%mod;
while(check(b*b-a)) {
b=rnd()%mod;
}
static mint val=b*b-a;
struct Complex {
mint real,imag;
Complex(mint treal=0,mint timag=0):real(treal),imag(timag) {}
Complex operator * (const Complex &rhs) {
return {real*rhs.real+imag*rhs.imag*val,real*rhs.imag+imag*rhs.real};
}
Complex& operator *= (const Complex &rhs) {
return *this=*this*rhs;
}
};
auto qpow=[&](Complex x,int y) {
Complex ans={1};
while(y) {
if(y&1) {
ans*=x;
}
x*=x;
y>>=1;
}
return ans;
};
mint ans=qpow({b,1},(mod+1)/2).real;
return min(ans,mod-ans);
}
};
struct Pow {
const int B=4e4;
mint p1[maxn];
mint p2[maxn];
mint pow(int y) {
return p1[y%B]*p2[y/B];
}
void prepare(mint p) {
p1[0]=1;
for(int i=1;i<=B;i++) {
p1[i]=p*p1[i-1];
}
mint ans=1;
for(int i=1;i<=B;i++) {
ans*=p;
}
p2[0]=1,p2[1]=ans;
for(int i=2;i<=B;i++) {
p2[i]=p2[i-1]*ans;
}
}
} pw;
using Complex=complex<double>;
using Poly=vector<mint>;
int t[maxn];
int mint::mod;
bool inited=false;
Poly s[sqrtn];
Poly l[sqrtn];
mint fact[maxn];
mint invf[maxn];
map<pii,Poly> mp;
void init(int p) {
mod=p;
mint::mod=p;
inited=true;
}
int extend(int x) {
int len=1;
while(len<x) {
len*=2;
}
return len;
}
void FFT(vector<Complex> &f,int op) {
int len=f.size();
for(int i=0;i<len;i++) {
t[i]=t[i>>1]>>1;
if(i&1) {
t[i]|=len>>1;
}
}
for(int i=0;i<len;i++) {
if(t[i]<i) {
swap(f[t[i]],f[i]);
}
}
for(int n=2;n<=len;n*=2) {
vector<Complex> ws(n/2);
for(int i=0;i<n/2;i++) {
ws[i]={cos(2*pi*i/n),sin(2*pi*i/n)*(!op?1:-1)};
}
for(int dt=0;dt<len;dt+=n) {
for(int i=0;i<n/2;i++) {
Complex t=ws[i]*f[i+n/2+dt];
f[i+n/2+dt]=f[i+dt]-t;
f[i+dt]=f[i+dt]+t;
}
}
}
}
void DFT(vector<Complex> &f) {
FFT(f,0);
}
void DFT(vector<Complex> &a,vector<Complex> &b) {
int len=a.size();
for(int i=0;i<len;i++) {
a[i].imag(b[i].real());
}
DFT(a);
b[0]=conj(a[0]);
for(int i=1;i<len;i++) {
b[i]=conj(a[len-i]);
}
for(int i=0;i<len;i++) {
Complex x=a[i],y=b[i];
a[i]=(x+y)/(Complex){2,0};
b[i]=(x-y)/(Complex){0,2};
}
}
void IDFT(vector<Complex> &f) {
FFT(f,1);
int len=f.size();
for(Complex &x:f) {
x/=len;
}
}
void IDFT(vector<Complex> &a,vector<Complex> &b) {
int len=a.size();
for(int i=0;i<len;i++) {
a[i]+=b[i]*(Complex){0,1};
}
IDFT(a);
for(int i=0;i<len;i++) {
b[i]=a[i].imag();
a[i].imag(0);
}
}
Poly mul(Poly ta,Poly tb,int p=-1) {
int n=ta.size(),m=tb.size(),len=extend(n+m-1);
if(p==-1) {
p=n+m-1;
}
if(n<=200||m<=200) {
Poly ans(n+m-1);
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
ans[i+j]+=ta[i]*tb[j];
}
}
ans.resize(p);
return ans;
}
vector<Complex> a,b,c,d;
int L=1<<15;
for(mint x:ta) {
a.push_back(x.val/L);
b.push_back(x.val%L);
}
for(mint x:tb) {
c.push_back(x.val/L);
d.push_back(x.val%L);
}
a.resize(len);
b.resize(len);
c.resize(len);
d.resize(len);
DFT(a,b),DFT(c,d);
for(int i=0;i<len;i++) {
Complex A=a[i],B=b[i],C=c[i],D=d[i];
a[i]=A*C;
b[i]=A*D+B*C;
c[i]=B*D;
}
IDFT(a,b),IDFT(c);
Poly ans(len);
auto get=[&](vector<Complex> &f,int i) -> int {
return (ll)(round(f[i].real()))%mint::mod;
};
for(int i=0;i<len;i++) {
ans[i]=(1ll*get(a,i)*L%mint::mod*L%mint::mod+1ll*get(b,i)*L%mint::mod+get(c,i))%mint::mod;
}
ans.resize(p);
return ans;
}
*/
void plus(Poly &a,Poly b) {
int n=a.size(),m=b.size();
a.resize(max(n,m));
for(int i=0;i<m;i++) {
a[i]+=b[i];
}
}
void sub(Poly &a,Poly b) {
int n=a.size(),m=b.size();
a.resize(max(n,m));
for(int i=0;i<m;i++) {
a[i]-=b[i];
}
}
Poly split(Poly &a,int n) {
Poly b;
for(int i=0;i<n&&i<a.size();i++) {
b.push_back(a[i]);
}
return b;
}
Poly inv(Poly a,int n=-1) {
assert(a[0].val);
if(n==-1) {
n=a.size();
}
Poly ans(1);
ans[0]=a[0].inv();
int len=1;
while(len<n) {
len*=2;
Poly t=ans;
for(mint &x:ans) {
x*=2;
}
sub(ans,mul(mul(t,t,len),split(a,len),len));
ans.resize(len);
}
ans.resize(n);
return ans;
}
Poly sqrt(Poly a,int n=-1) {
if(n==-1) {
n=a.size();
}
Poly ans(1);
ans[0]=a[0].sqrt();
int len=1;
while(len<n) {
len*=2;
Poly t=ans;
for(mint &x:t) {
x*=2;
}
ans=mul(ans,ans,len);
plus(ans,split(a,len));
ans=mul(ans,inv(t,len),len);
ans.resize(len);
}
ans.resize(n);
return ans;
}
Poly diff(Poly a) {
Poly ans(a.size()-1);
for(int i=0;i+1<a.size();i++) {
ans[i]=a[i+1]*(i+1);
}
return ans;
}
void pfact(int n) {
fact[0]=invf[0]=1;
for(int i=1;i<=n;i++) {
fact[i]=fact[i-1]*i;
}
invf[n]=fact[n].inv();
for(int i=n-1;i>=1;i--) {
invf[i]=invf[i+1]*(i+1);
}
}
Poly inte(Poly a) {
Poly ans(a.size()+1);
pfact(a.size());
for(int i=0;i<a.size();i++) {
ans[i+1]=a[i]*invf[i+1]*fact[i];
}
return ans;
}
Poly ln(Poly a,int n=-1) {
assert(a[0]==1);
if(n==-1) {
n=a.size();
}
return inte(mul(diff(a),inv(a,n),n-1));
}
Poly exp(Poly a,int n=-1) {
assert(!a[0].val);
if(n==-1) {
n=a.size();
}
Poly ans(1);
ans[0]=1;
int len=1;
while(len<n) {
len*=2;
Poly t=ln(ans,len);
for(mint &x:t) {
x=0-x;
}
plus(t,split(a,len));
t[0]+=1;
ans=mul(ans,t);
ans.resize(len);
}
ans.resize(n);
return ans;
}
Poly merge(Poly a,Poly b) {
// return : length = n
int n=a.size(),B=std::sqrt(n)*2;
s[0].resize(n),s[0][0]=1;
s[1]=b,s[1].resize(n);
for(int i=2;i<B;i++) {
s[i]=mul(s[i-1],b,n);
}
l[0].resize(n),l[0][0]=1;
l[1]=mul(b,s[B-1],n);
for(int i=2;i<=n/B;i++) {
l[i]=mul(l[i-1],l[1],n);
}
Poly ans(n);
for(int i=0;i<=n/B;i++) {
Poly t(n);
for(int j=0;j<B&&i*B+j<n;j++) {
mint x=a[i*B+j];
int k=0;
for(;k+3<n;k+=4) {
t[k]+=x*s[j][k];
t[k+1]+=x*s[j][k+1];
t[k+2]+=x*s[j][k+2];
t[k+3]+=x*s[j][k+3];
}
for(;k<n;k++) {
t[k]+=x*s[j][k];
}
}
plus(ans,mul(t,l[i],n));
}
return ans;
}
Poly pow(Poly a,int k,int n=-1) {
// a[0] = 1 must hold
if(n==-1) {
n=a.size();
}
a=ln(a);
for(mint &x:a) {
x*=k;
}
return exp(a);
}
Poly pow(Poly a,int m1,int m2,double m3,int n=-1) {
// m1: mod p
// m2: mod phi(p)
// m3: real p
if(n==-1) {
n=a.size();
}
int mv;
bool f=false;
mint p;
for(int i=0;i<a.size();i++) {
if(a[i].val) {
f=true;
if(i*m3>=n) {
Poly e(n);
return e;
}
mv=(int)(m3)*i;
p=a[i];
mint inv=a[i].inv();
for(mint &x:a) {
x*=inv;
}
for(int j=0;j+i<a.size();j++) {
a[j]=a[j+i];
}
for(int j=1;j<=i;j++) {
a.pop_back();
}
for(int j=1;j<=i;j++) {
a.push_back(0);
}
break;
}
}
if(!f) {
return a;
}
a=ln(a);
for(mint &x:a) {
x*=m1;
}
a=exp(a);
for(mint &x:a) {
x*=p.qpow(m2);
}
for(int i=a.size();i>=mv;i--) {
a[i]=a[i-mv];
}
for(int i=0;i<mv;i++) {
a[i]=0;
}
return a;
}
Poly sum(Poly a,int k,int n=-1) {
if(n==-1) {
n=a.size();
}
Poly b(n);
b[0]=1;
pfact(n);
for(int i=1;i<n;i++) {
b[i]=1ll*b[i-1]*(k+i-1)*fact[i-1]*invf[i];
}
return mul(a,b,n);
}
Poly diff(Poly a,int k,int n=-1) {
if(n==-1) {
n=a.size();
}
Poly b(n);
b[0]=1;
pfact(n);
for(int i=1;i<n;i++) {
b[i]=1ll*b[i-1]*(k-i+1)*fact[i-1]*invf[i]*(-1);
}
return mul(a,b,n);
}
Poly rev(Poly a) {
reverse(a.begin(),a.end());
return a;
}
pair<Poly,Poly> div(Poly a,Poly b) {
int n=a.size(),m=b.size();
a=rev(a),b=rev(b);
Poly c=mul(a,inv(b,n-m+1),n-m+1);
c=rev(c);
a=rev(a);
sub(a,mul(rev(b),c));
a.resize(m-1);
return {c,a};
}
Poly getv(Poly a,Poly b) {
function<void(int,int)> build=[&](int l,int r) {
if(l==r) {
mp[{l,r}]={0-b[l],1};
return ;
}
int mid=(l+r)>>1;
build(l,mid);
build(mid+1,r);
mp[{l,r}]=mul(mp[{l,mid}],mp[{mid+1,r}]);
};
int m=b.size();
build(0,m-1);
Poly ans(m);
function<void(Poly,int,int)> solve=[&](Poly f,int l,int r) {
if(l==r) {
ans[l]=f[0];
return ;
}
int mid=(l+r)>>1;
solve(div(f,mp[{l,mid}]).sec,l,mid);
solve(div(f,mp[{mid+1,r}]).sec,mid+1,r);
};
solve(a,0,m-1);
return ans;
}
Poly getf(Poly x,Poly y) {
function<Poly(int,int)> calc=[&](int l,int r) -> Poly {
if(l==r) {
return {0-x[l],1};
}
int mid=(l+r)>>1;
return mul(calc(l,mid),calc(mid+1,r));
};
int n=x.size();
Poly m=calc(0,n-1);
m=diff(m);
Poly v=getv(m,x);
for(int i=0;i<n;i++) {
v[i]=y[i]/v[i];
}
function<pair<Poly,Poly>(int,int)> solve=[&](int l,int r) -> pair<Poly,Poly> {
if(l==r) {
return {{0-x[l],1},{v[l]}};
}
int mid=(l+r)>>1;
auto al=solve(l,mid),ar=solve(mid+1,r);
Poly ml=al.fir,fl=al.sec,mr=ar.fir,fr=ar.sec,t=mul(fl,mr);
plus(t,mul(fr,ml));
return {mul(ml,mr),t};
};
return solve(0,n-1).sec;
}
Poly sin(Poly a) {
mint i=mint(-1).sqrt();
for(mint &x:a) {
x*=i;
}
Poly ans=exp(a);
for(mint &x:a) {
x*=-1;
}
sub(ans,exp(a));
mint inv=mint(2).inv()*i.inv();
for(mint &x:ans) {
x*=inv;
}
return ans;
}
Poly cos(Poly a) {
mint i=mint(-1).sqrt();
for(mint &x:a) {
x*=i;
}
Poly ans=exp(a);
for(mint &x:a) {
x*=-1;
}
plus(ans,exp(a));
mint inv=mint(2).inv();
for(mint &x:ans) {
x*=inv;
}
return ans;
}
Poly asin(Poly a) {
int n=a.size();
Poly t=diff(a);
a=mul(a,a,n-1);
for(mint &x:a) {
x=0-x;
}
a[0]+=1;
return inte(mul(t,inv(sqrt(a,n-1),n-1),n-1));
}
Poly atan(Poly a) {
int n=a.size();
Poly t=diff(a);
a=mul(a,a,n-1);
a[0]+=1;
return inte(mul(t,inv(a,n-1),n-1));
}
Poly Z(Poly a,mint c,int m=-1) {
if(m==-1) {
m=a.size();
}
// a(c^0), a(c^1), ..., a(c^{m-1})
int n=a.size();
Poly t(n+m);
vector<int> C(n+m);
pw.prepare(c);
for(int i=0;i<=n+m-1;i++) {
C[i]=1ll*i*(i-1)/2%(mod-1);
t[i]=pw.pow(C[i]);
}
for(int i=0;i<n;i++) {
a[i]*=pw.pow((-C[i]+mod-1)%(mod-1));
}
a=mul(a,rev(t));
Poly ans;
for(int i=m+n-1;i>=n;i--) {
ans.push_back(a[i]);
}
for(int i=0;i<m;i++) {
ans[i]*=pw.pow((-C[i]+mod-1)%(mod-1));
}
return ans;
}
Poly omultiset(Poly a,int m) {
pfact(m);
auto inv=[&](int x) {
return fact[x-1]*invf[x];
};
Poly b(m+1);
for(int i=1;i<a.size();i++) {
for(int n=1;i*n<=m;n++) {
b[i*n]+=a[i]*inv(n);
}
}
Poly ans=exp(b);
ans.resize(m+1);
return ans;
}
istream& operator >> (istream &is,Poly &f) {
for(mint &x:f) {
is>>x;
}
return is;
}
ostream& operator << (ostream &os,Poly f) {
for(int i=0;i<f.size();i++) {
os<<f[i];
if(i!=f.size()-1) {
os<<" ";
}
}
return os;
}
}
using namespace poly;
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
n++;
m++;
Poly f(a, a + n);
Poly g(b, b + m);
f = mul(f, g);
for (int i = 0; i < (int) f.size(); i++) {
c[i] = f[i].val;
}
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 17.654 ms | 111 MB + 408 KB | Runtime Error | Score: 0 | 显示更多 |