QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#642530 | #620. 多项式对数函数 | Zhou_JK | 100 ✓ | 542ms | 78684kb | C++23 | 16.5kb | 2024-10-15 14:48:24 | 2024-10-15 14:48:32 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cassert>
#include<ctime>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
using namespace std;
namespace Polynomial
{
constexpr int g=3;
constexpr int MOD=998244353;
int add(int a,int b)
{
a+=b;
return a>=MOD?a-MOD:a;
}
int sub(int a,int b)
{
return a>=b?a-b:a+MOD-b;
}
int qpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=(long long)res*a%MOD;
a=(long long)a*a%MOD,b>>=1;
}
return res;
}
int getinv(int x)
{
return qpow(x,MOD-2);
}
typedef vector<int> Poly;
Poly operator+(const Poly &a,const Poly &b)
{
Poly f=a,g=b;
int n=max(a.size(),b.size());
f.resize(n),g.resize(n);
Poly c(n);
for(int i=0;i<n;i++)
{
c[i]=f[i]+g[i];
if(c[i]>=MOD) c[i]-=MOD;
}
return c;
}
Poly operator-(const Poly &a,const Poly &b)
{
Poly f=a,g=b;
int n=max(a.size(),b.size());
f.resize(n),g.resize(n);
Poly c(n);
for(int i=0;i<n;i++)
{
c[i]=f[i]-g[i];
if(c[i]<0) c[i]+=MOD;
}
return c;
}
Poly operator+(const Poly &F,const int &x)
{
Poly f=F;
f[0]+=x;
if(f[0]>=MOD) f[0]-=MOD;
return f;
}
Poly operator+(const int &x,const Poly &F)
{
Poly f=F;
f[0]+=x;
if(f[0]>=MOD) f[0]-=MOD;
return f;
}
Poly operator-(const Poly &F,const int &x)
{
Poly f=F;
f[0]-=x;
if(f[0]<0) f[0]+=MOD;
return f;
}
Poly operator-(const int &x,const Poly &F)
{
Poly f=F;
int n=f.size()-1;
for(int i=0;i<=n;i++)
f[i]=MOD-f[i];
f[0]+=x;
if(f[0]>=MOD) f[0]-=MOD;
return f;
}
int gw[(1<<21)+1];
vector<int>inv;
void init(int _n)
{
static int n=1;
if(_n<n) return;
int t=1;
while((1<<t)<_n) t++;
t=min(t-1,21);
gw[0]=1,gw[1<<t]=qpow(31,1<<(21-t));
for(int i=t;i>0;i--)
gw[1<<(i-1)]=(long long)gw[1<<i]*gw[1<<i]%MOD;
for(int i=1;i<(1<<t);i++)
gw[i]=(long long)gw[i&(i-1)]*gw[i&-i]%MOD;
inv.resize(_n+1);
inv[1]=1;
for(int i=2;i<=_n;i++)
inv[i]=(long long)(MOD-MOD/i)*inv[MOD%i]%MOD;
n=_n;
return;
}
constexpr int BIT=10;
void dft(Poly &F,int _n)
{
int n=1;
while(n<_n) n<<=1;
init(n);
F.resize(n);
vector<unsigned long long>f(n);
for(int i=0;i<n;i++)
f[i]=F[i];
for(int len=n;len>1;len>>=1)
{
if((len>>BIT)&1)
{
for(int i=0;i<n;i++)
f[i]%=MOD;
}
for(int i=0,*w=gw;i<n;i+=len,w++)
for(int k=i;k<i+(len>>1);k++)
{
unsigned long long l=f[k];
int r=(*w)*f[k+(len>>1)]%MOD;
f[k]=l+r;
f[k+(len>>1)]=l+MOD-r;
}
}
for(int i=0;i<n;i++)
F[i]=f[i]%MOD;
return;
}
void idft(Poly &F,int _n)
{
int n=1;
while(n<_n) n<<=1;
init(n);
F.resize(n);
vector<unsigned long long>f(n);
for(int i=0;i<n;i++)
f[i]=F[i];
for(int len=2;len<=n;len<<=1)
{
if((len>>BIT)&1)
{
for(int i=0;i<n;i++)
f[i]%=MOD;
}
for(int i=0,*w=gw;i<n;i+=len,w++)
for(int k=i;k<i+(len>>1);k++)
{
unsigned long long l=f[k];
int r=f[k+(len>>1)]%MOD;
f[k]=l+r;
f[k+(len>>1)]=(l+MOD-r)*(*w)%MOD;
}
}
int invn=getinv(n);
for(int i=0;i<n;i++)
F[i]=f[i]%MOD*invn%MOD;
reverse(F.begin()+1,F.end());
return;
}
Poly ntt(const Poly &F,const Poly &G,const function<int(int,int)> &mul)
{
Poly f=F,g=G;
int n=f.size()-1,m=g.size()-1;
m+=n,n=1;
while(n<=m) n<<=1;
f.resize(n);
g.resize(n);
dft(f,n);
dft(g,n);
for(int i=0;i<n;i++)
f[i]=mul(f[i],g[i]);
idft(f,n);
f.resize(m+1);
return f;
}
Poly operator*(const Poly &F,const Poly &G)
{
Poly f=F,g=G;
int n=f.size()-1,m=g.size()-1;
m+=n,n=1;
while(n<=m) n<<=1;
f.resize(n);
g.resize(n);
dft(f,n);
dft(g,n);
for(int i=0;i<n;i++)
f[i]=(long long)f[i]*g[i]%MOD;
idft(f,n);
f.resize(m+1);
return f;
}
Poly operator*(const Poly &F,const int &x)
{
Poly f=F;
int n=f.size()-1;
for(int i=0;i<=n;i++)
f[i]=(long long)f[i]*x%MOD;
return f;
}
Poly operator*(const int &x,const Poly &F)
{
Poly f=F;
int n=f.size()-1;
for(int i=0;i<=n;i++)
f[i]=(long long)f[i]*x%MOD;
return f;
}
Poly getinv(const Poly &F)
{
Poly f=F;
int m=f.size()-1;
int n=1;
while(n<=m) n<<=1;
f.resize(n);
Poly g={getinv(f[0])};
for(int m=2;m<=n;m<<=1)
{
Poly t(f.begin(),f.begin()+m);
g=ntt(t,g,[&](const int &x,const int &y){return sub(add(y,y),(long long)y*y%MOD*x%MOD);});
g.resize(m);
}
g.resize(m+1);
return g;
}
int w;
struct Complex
{
int real,imag;
bool operator ==(const Complex &b)const
{
return real==b.real&&imag==b.imag;
}
Complex operator *(const Complex &b)const
{
Complex res;
res.real=((long long)real*b.real+(long long)w*imag%MOD*b.imag)%MOD;
res.imag=((long long)real*b.imag+(long long)imag*b.real)%MOD;
return res;
}
friend Complex qpow(Complex a,int b)
{
Complex res=(Complex){1,0};
while(b)
{
if(b&1) res=res*a;
a=a*a,b>>=1;
}
return res;
}
};
int cipolla(int n)
{
static mt19937 myrand(time(NULL));
if(n==0) return 0;
function<bool(int)>check=[&](const int &n){return qpow(n,(MOD-1)/2)==1;};
if(!check(n)) return -1;
int a=myrand()%(MOD-1)+1;
while(check(((long long)a*a-n+MOD)%MOD)) a=myrand()%(MOD-1)+1;
w=((long long)a*a-n+MOD)%MOD;
Complex res=qpow((Complex){a,1},(MOD+1)/2);
return res.real;
}
Poly sqrt(const Poly &F)
{
Poly f=F;
int m=f.size()-1;
int n=1;
while(n<=m) n<<=1;
f.resize(n);
int g0=cipolla(f[0]);
Poly g={min(g0,MOD-g0)};
int inv2=getinv(2);
for(int m=2;m<=n;m<<=1)
{
Poly t(f.begin(),f.begin()+m);
g.resize(m);
g=g*inv2+ntt(t,getinv(g),[&](const int &x,const int &y){return (long long)inv2*x%MOD*y%MOD;});
g.resize(m);
}
g.resize(m+1);
return g;
}
Poly operator/(const Poly &F,const Poly &G)
{
Poly f=F,g=G;
int n=f.size()-1,m=g.size()-1;
if(n<m) return Poly(n-m+1,0);
reverse(f.begin(),f.end());
reverse(g.begin(),g.end());
f.resize(n-m+1);
g.resize(n-m+1);
Poly q=f*getinv(g);
q.resize(n-m+1);
reverse(q.begin(),q.end());
return q;
}
Poly operator%(const Poly &F,const Poly &G)
{
Poly f=F,g=G,q=f/g;
int m=g.size()-1;
g.resize(m);
q.resize(m);
Poly c=g*q;
c.resize(m);
f.resize(m);
return f-c;
}
Poly diff_calc(const Poly &F)
{
Poly f=F;
int n=f.size()-1;
Poly g(n);
for(int i=1;i<=n;i++)
g[i-1]=(long long)f[i]*i%MOD;
return g;
}
Poly inte_calc(const Poly &G)
{
Poly g=G;
int n=g.size()-1;
init(n+2);
Poly f(n+2);
for(int i=1;i<=n+1;i++)
f[i]=(long long)g[i-1]*inv[i]%MOD;
return f;
}
Poly ln(const Poly &F)
{
Poly f=F;
int n=f.size()-1;
Poly g=diff_calc(f)*getinv(f);
g.resize(n+1);
g=inte_calc(g);
g.resize(n+1);
return g;
}
Poly exp(const Poly &F)
{
Poly f=F;
int m=f.size()-1;
int n=1;
while(n<=m) n<<=1;
f.resize(n);
Poly g={1};
for(int m=2;m<=n;m<<=1)
{
Poly t(f.begin(),f.begin()+m);
Poly s=g;
g.resize(m);
g=s*(t-ln(g)+(Poly){1});
g.resize(m);
}
g.resize(m+1);
return g;
}
Poly qpow(const Poly &F,const int &k)
{
Poly f=F;
int n=f.size()-1;
Poly g(n+1);
int pos=-1;
for(int i=0;i<=n;i++)
if(f[i]>0)
{
g[i]=f[i];
pos=i;
break;
}
if(pos==-1) return g;
int mu=f[pos],invm=getinv(mu);
for(int i=0;i<=n-pos;i++)
f[i]=(long long)f[i+pos]*invm%MOD;
for(int i=n-pos+1;i<=n;i++)
f[i]=0;
g[pos]=0;
if((long long)pos*k<=n||pos==0)
{
g=exp(k*ln(f));
int v=qpow(mu,k);
for(int i=n;i>=pos*k;i--)
g[i]=(long long)g[i-pos*k]*v%MOD;
for(int i=pos*k-1;i>=0;i--)
g[i]=0;
}
return g;
}
int poly_calc(const Poly &F,const int &x)
{
Poly f=F;
int n=f.size()-1;
int fc=1,res=0;
for(int i=0;i<=n;i++)
res=(res+(long long)f[i]*fc)%MOD,fc=(long long)fc*x%MOD;
return res;
}
Poly mul_t(const Poly &g,const Poly &f)
{
assert(g.size()<=f.size());
int m=g.size()-1;
Poly gt=g;
reverse(gt.begin(),gt.end());
Poly h=gt*f;
Poly res(f.size());
for(int i=0;i<(int)f.size();i++)
res[i]=h[m+i];
return res;
}
Poly poly_multiple_point_evaluation(const Poly &F,const Poly &A)
{
Poly f=F,a=A;
int m=max(f.size()-1,a.size());
f.resize(m+1),a.resize(m);
vector<Poly>g(m<<2);
function<void(int,int,int)> poly_multiple_point_evaluation_init=[&](int i,int l,int r)->void
{
if(l==r)
{
g[i].resize(2);
g[i][0]=1,g[i][1]=a[l]==0?0:MOD-a[l];
return;
}
int mid=(l+r)/2;
poly_multiple_point_evaluation_init(i*2,l,mid);
poly_multiple_point_evaluation_init(i*2+1,mid+1,r);
g[i]=g[i*2]*g[i*2+1];
return;
};
poly_multiple_point_evaluation_init(1,0,m-1);
Poly v(A.size());
function<void(int,int,int,const Poly&)>poly_multiple_point_evaluation_solve=[&](int i,int l,int r,const Poly &F)->void
{
if(l>=(int)A.size()) return;
if(l==r)
{
v[l]=F[0];
return;
}
int mid=(l+r)/2;
Poly hl=mul_t(g[i*2+1],F),hr=mul_t(g[i*2],F);
hl.resize(mid-l+1),hr.resize(r-mid);
poly_multiple_point_evaluation_solve(i*2,l,mid,hl);
poly_multiple_point_evaluation_solve(i*2+1,mid+1,r,hr);
return;
};
Poly h=mul_t(getinv(g[1]),f);
h.resize(m);
poly_multiple_point_evaluation_solve(1,0,m-1,h);
return v;
}
Poly poly_inte(const vector<pair<int,int>> &p)
{
int n=p.size()-1;
vector<Poly>g(n<<2);
function<void(int,int,int)> init_poly_eval=[&](int i,int l,int r)
{
if(l==r)
{
g[i]=(Poly){MOD-p[l].first,1};
return;
}
int mid=(l+r)/2;
init_poly_eval(i*2,l,mid);
init_poly_eval(i*2+1,mid+1,r);
g[i]=g[i*2]*g[i*2+1];
return;
};
init_poly_eval(1,0,n);
Poly x(n+1);
for(int i=0;i<=n;i++)
x[i]=p[i].first;
Poly F=poly_multiple_point_evaluation(diff_calc(g[1]),x);
vector<int> a(n+1);
for(int i=0;i<=n;i++)
a[i]=(long long)p[i].second*getinv(F[i])%MOD;
vector<Poly>res(n<<2);
function<void(int,int,int)> solve_poly_inte=[&](int i,int l,int r)
{
if(l==r)
{
res[i]={a[l]};
return;
}
int mid=(l+r)/2;
solve_poly_inte(i*2,l,mid);
solve_poly_inte(i*2+1,mid+1,r);
res[i]=res[i*2]*g[i*2+1]+res[i*2+1]*g[i*2];
return;
};
solve_poly_inte(1,0,n);
return res[1];
}
Poly or_convolution(const Poly &F,const Poly &G)
{
Poly f=F,g=G;
int m=max(f.size()-1,g.size()-1),n=1;
while(n<=m) n<<=1;
f.resize(n),g.resize(n);
auto fwt=[&](Poly &F)
{
int n=F.size();
for(int len=2;len<=n;len<<=1)
for(int i=0;i<n;i+=len)
for(int k=i;k<i+(len>>1);k++)
F[k+(len>>1)]=add(F[k+(len>>1)],F[k]);
return;
};
fwt(f);
fwt(g);
for(int i=0;i<n;i++)
f[i]=(long long)f[i]*g[i]%MOD;
auto ifwt=[&](Poly &F)
{
int n=F.size();
for(int len=2;len<=n;len<<=1)
for(int i=0;i<n;i+=len)
for(int k=i;k<i+(len>>1);k++)
F[k+(len>>1)]=sub(F[k+(len>>1)],F[k]);
return;
};
ifwt(f);
return f;
}
Poly and_convolution(const Poly &F,const Poly &G)
{
Poly f=F,g=G;
int m=max(f.size()-1,g.size()-1),n=1;
while(n<=m) n<<=1;
f.resize(n),g.resize(n);
function<void(Poly &)> fwt=[&](Poly &F)
{
int n=F.size();
for(int len=2;len<=n;len<<=1)
for(int i=0;i<n;i+=len)
for(int k=i;k<i+(len>>1);k++)
F[k]=add(F[k],F[k+(len>>1)]);
return;
};
fwt(f);
fwt(g);
for(int i=0;i<n;i++)
f[i]=(long long)f[i]*g[i]%MOD;
function<void(Poly &)> ifwt=[&](Poly &F)
{
int n=F.size();
for(int len=2;len<=n;len<<=1)
for(int i=0;i<n;i+=len)
for(int k=i;k<i+(len>>1);k++)
F[k]=sub(F[k],F[k+(len>>1)]);
return;
};
ifwt(f);
return f;
}
Poly xor_convolution(const Poly &F,const Poly &G)
{
Poly f=F,g=G;
int m=max(f.size()-1,g.size()-1),n=1;
while(n<=m) n<<=1;
f.resize(n),g.resize(n);
function<void(Poly &)> fwt=[&](Poly &F)
{
int n=F.size();
for(int len=2;len<=n;len<<=1)
for(int i=0;i<n;i+=len)
for(int k=i;k<i+(len>>1);k++)
{
int l=F[k],r=F[k+(len>>1)];
F[k]=add(l,r);
F[k+(len>>1)]=sub(l,r);
}
return;
};
fwt(f);
fwt(g);
for(int i=0;i<n;i++)
f[i]=(long long)f[i]*g[i]%MOD;
function<void(Poly &)> ifwt=[&](Poly &F)
{
int n=F.size();
for(int len=2;len<=n;len<<=1)
for(int i=0;i<n;i+=len)
for(int k=i;k<i+(len>>1);k++)
{
int l=F[k],r=F[k+(len>>1)];
F[k]=add(l,r);
F[k+(len>>1)]=sub(l,r);
}
int invn=getinv(n);
for(int i=0;i<(int)F.size();i++)
F[i]=(long long)F[i]*invn%MOD;
return;
};
ifwt(f);
return f;
}
int &reduce(int &x)
{
return x+=x>>31&MOD;
}
Poly subset_convolution(const Poly &F,const Poly &G)
{
int m=max(F.size()-1,G.size()-1),n=1,c=1;
while(n<=m) n<<=1,c++;
vector<Poly> f(c+1,Poly(n,0)),g(c+1,Poly(n,0));
for(int i=0;i<(int)F.size();i++)
f[__builtin_popcount(i)][i]=F[i];
for(int i=0;i<(int)G.size();i++)
g[__builtin_popcount(i)][i]=G[i];
function<void(Poly &)> fwt=[&](Poly &F)
{
int n=F.size();
for(int len=2;len<=n;len<<=1)
for(int i=0;i<n;i+=len)
for(int k=i;k<i+(len>>1);k++)
{
int l=F[k],r=F[k+(len>>1)];
F[k]=add(l,r);
F[k+(len>>1)]=sub(l,r);
}
return;
};
for(int i=0;i<=c;i++)
fwt(f[i]),fwt(g[i]);
vector<Poly> h(c+1,Poly(n,0));
for(int i=0;i<=c;i++)
for(int j=0;j<=i;j++)
{
int k=i-j;
for(int s=0;s<n;s++)
h[i][s]=(h[i][s]+(long long)f[j][s]*g[k][s])%MOD;
}
function<void(Poly &)> ifwt=[&](Poly &F)
{
int n=F.size();
for(int len=2;len<=n;len<<=1)
for(int i=0;i<n;i+=len)
for(int k=i;k<i+(len>>1);k++)
{
int l=F[k],r=F[k+(len>>1)];
F[k]=add(l,r);
F[k+(len>>1)]=sub(l,r);
}
int invn=getinv(n);
for(int i=0;i<(int)F.size();i++)
F[i]=(long long)F[i]*invn%MOD;
return;
};
for(int i=0;i<=c;i++)
ifwt(h[i]);
Poly res(n);
for(int i=0;i<n;i++)
res[i]=h[__builtin_popcount(i)][i];
return res;
}
Poly cyclic_convolution(const Poly &a,const Poly &b)
{
assert(a.size()==b.size());
int n=a.size();
Poly c=a*b;
for(int i=n;i<(int)c.size();i++)
c[i-n]=add(c[i],c[i-n]);
c.resize(n);
return c;
}
}
using namespace Polynomial;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int n;
cin>>n;
Poly f(n);
for(int i=0;i<n;i++)
cin>>f[i];
Poly g=ln(f);
for(int u:g)
cout<<u<<" ";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 20
Accepted
time: 1ms
memory: 3704kb
input:
100 1 961880754 72654790 829592288 646635609 311233105 453229378 664750040 147019368 89089702 319123224 785184513 130058112 232462250 915136660 400585378 710632575 470300421 785452776 22895339 267215672 816821438 688384368 814593296 401856501 121390605 474566074 229876909 179995671 479480781 1150666...
output:
0 961880754 109050820 910057683 452181005 796593970 362074759 53194053 540144365 291711835 996774416 338261551 172006522 156841252 598600919 311016398 440325847 20403335 269495509 528824266 723093435 143651758 274603604 232097861 366573798 240410404 263548039 813262296 718323828 688147861 784480664 ...
result:
ok 100 numbers
Test #2:
score: 20
Accepted
time: 4ms
memory: 3976kb
input:
5000 1 18893689 800248942 590834626 422952919 370806502 832521768 157416021 449498617 50268466 481346733 588328257 836431005 172279377 701248316 688081741 641390799 971605524 529682685 15073211 370474889 330708737 461612260 427248257 124799236 2295287 579063610 911278897 850964373 680664511 61289593...
output:
0 18893689 649428805 738833568 120891255 19670140 608054187 781421921 559764661 292759237 202235517 465634637 516704148 737098204 892179011 495729143 603364788 154939005 564276135 247402588 951327329 502706506 503981602 661783358 672492854 55298928 349262035 379325690 748797260 36812211 286288663 84...
result:
ok 5000 numbers
Test #3:
score: 20
Accepted
time: 12ms
memory: 5948kb
input:
30000 1 970882639 503981013 404846066 863588691 801944716 361233000 107564825 85420624 950377978 209112662 646496760 470328364 139325904 593853922 301851602 265141963 464762654 225023703 474139631 555855644 900153878 865682768 387642831 292054593 592453364 468382456 907565611 122026085 280142449 472...
output:
0 970882639 457403585 873878370 318261289 5420793 914065224 347039061 368768664 63992668 817003966 398719209 868368828 188152960 579963976 211917006 499838248 97901028 786777661 15634701 242132107 434131354 537665508 126497027 873212165 645988134 766323255 611262222 83799227 780873982 171681961 5453...
result:
ok 30000 numbers
Test #4:
score: 20
Accepted
time: 60ms
memory: 12988kb
input:
100000 1 636749537 301358055 13535739 884134558 389669951 669242330 226185280 157140037 941409936 290390837 486338369 9840834 587277544 277161163 427234947 202859695 898077735 682355257 509533156 571238511 227077530 100718382 191992899 462596953 832899262 101253983 596098985 595161513 259772722 4995...
output:
0 636749537 893745725 208856897 833356726 645101318 331081085 674809362 376515893 529729696 159424368 64304300 38260664 651978624 757150457 656660176 981816671 482124761 664996997 340575888 544387934 224993025 630282066 889077734 595392417 65927703 145196506 381507561 80669600 779290852 657316164 76...
result:
ok 100000 numbers
Test #5:
score: 20
Accepted
time: 542ms
memory: 78684kb
input:
1000000 1 785396418 410648986 62677121 16031158 710742216 677635002 789886669 737278658 655583592 459342332 542680522 553715144 799887527 99957827 533567330 838324845 788131790 637348498 428285164 429527739 233116765 772393666 138968071 917779658 494447494 910763455 642522636 855227115 698468466 219...
output:
0 785396418 121390930 573141379 208264134 820348528 437016261 369027464 119111821 432492474 342634043 694859972 192041833 336177730 969184881 829638906 173117766 779517533 982980311 517238274 459092122 579250908 924006190 697936237 885177047 350279990 695355377 923665009 83389011 582391001 956169113...
result:
ok 1000000 numbers