QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#381587 | #6196. Minimum Element Problem | JohnAlfnov | RE | 0ms | 0kb | C++14 | 5.4kb | 2024-04-07 19:07:29 | 2024-04-07 19:07:30 |
answer
//Code by Lightningfall
//Start coding on ????/??/??
//Finish debugging on ????/??/??
#include<bits/stdc++.h>
#define mod 998244353
#define poly vector<int>
#define N 21
using namespace std;
void output(poly a){
for(auto cu:a)printf("%d ",cu);
printf("\n");
}
poly mul(int k,poly a){
int sz=a.size();
poly b;
for(int i=0;i<sz;++i)b.emplace_back(1ll*k*a[i]%mod);
return b;
}
poly plu(poly a,poly b){
poly c;
int s1=a.size(),s2=b.size();
c.resize(max(s1,s2));
for(int i=0;i<s1;++i)c[i]=(c[i]+a[i])%mod;
for(int i=0;i<s2;++i)c[i]=(c[i]+b[i])%mod;
return c;
}
int powdv(int x,int y=mod-2){
int ans=1;
while(y){
if(y&1)ans=1ll*ans*x%mod;
y>>=1,x=1ll*x*x%mod;
}
return ans;
}
int a[1<<N],b[1<<N],ap[1<<N],bp[1<<N];
int rev[1<<N];
void getrev(int l){
rev[0]=0;
for(int i=1;i<=l;++i){
for(int j=0;j<(1<<(i-1));++j){
rev[j^(1<<(i-1))]=rev[j]^(1<<(l-i));
}
}
}
void ntt(int l,int *c,int *d,int cd){
for(int i=0;i<(1<<l);++i)d[i]=c[rev[i]];
for(int i=1;i<(1<<l);i<<=1){
int o1=powdv(3,(mod-1)/i/2);
if(cd==-1)o1=powdv(o1);
for(int j=0;j<(1<<l);j+=i+i){
int o=1;
for(int k=j;k<j+i;++k){
int A=d[k],B=d[k+i];
d[k]=(A+1ll*o*B)%mod,d[k+i]=(A-1ll*o*B)%mod;
o=1ll*o*o1%mod;
}
}
}
if(cd==-1){
int ny=powdv(1<<l);
for(int i=0;i<(1<<l);++i)d[i]=1ll*d[i]*ny%mod;
}
}
poly multi(vector<poly>g){
int sz=0;
for(auto p:g)sz+=p.size()-1;
int ss=sz+1;
while(ss&(ss-1))++ss;
int l=__builtin_ctz(ss);
getrev(l);
for(int i=0;i<(1<<l);++i)ap[i]=1;
for(auto p:g){
int zz=p.size();
for(int i=0;i<(1<<l);++i){
a[i]=(i<zz?p[i]:0);
}
ntt(l,a,bp,1);
for(int i=0;i<(1<<l);++i)ap[i]=1ll*ap[i]*bp[i]%mod;
}
ntt(l,ap,b,-1);
poly ans;
for(int i=0;i<=sz;++i)ans.emplace_back((b[i]+mod)%mod);
return ans;
}
poly deri(poly a){
if((signed)a.size()==1)return {0};
int sz=a.size();
poly b;
for(int i=1;i<sz;++i)b.emplace_back(1ll*i*a[i]%mod);
return b;
}
int id[1<<N],di[1<<N],ny[1<<N];
int C(int n,int m){
if(n<0||m<0||n<m)return 0;
return 1ll*di[n]*id[m]%mod*id[n-m]%mod;
}
void init(int sz){
di[0]=1;
for(int i=1;i<=sz;++i)di[i]=1ll*i*di[i-1]%mod;
id[sz]=powdv(di[sz]);
for(int i=sz-1;i>=0;--i)id[i]=1ll*id[i+1]*(i+1)%mod;
for(int i=1;i<=sz;++i)ny[i]=1ll*id[i]*di[i-1]%mod;
}
poly inte(poly a){
int sz=a.size();
init(sz);
poly b;
b.emplace_back(0);
for(int i=0;i<sz;++i)b.emplace_back(1ll*ny[i+1]*a[i]%mod);
return b;
}
poly mo(poly a,int n){
poly b;
int sz=min((signed)a.size(),n);
for(int i=0;i<sz;++i)b.emplace_back(a[i]);
return b;
}
poly inver(poly a,poly b,int n,int cs){
if(cs==0)return b;
int zz=min(2*(signed)b.size(),n);
b=mo(plu(mul(2,b),mul(mod-1,multi({b,b,mo(a,2*b.size())}))),zz);
return inver(a,b,n,cs-1);
}
poly inv(poly a,int n){
poly b={1};
int cc=1,gs=1;
while(cc<=n)cc*=2,++gs;
return inver(a,b,n,gs);
}
poly ln(poly a){
poly pp=mo(multi({deri(a),inv(a,a.size())}),a.size()-1);
return inte(pp);
}
const int B=16;
int aa[500005],bb[500005];
void solve(int l,int r){
if(r-l<=50){
for(int i=l;i<r;++i){
int he=0;
for(int j=l;j<i;++j){
he=(he+1ll*bb[j]*aa[i-j])%mod;
}
bb[i]=1ll*(bb[i]+he)*ny[i]%mod;
}
return;
}
int fd[B+5];
for(int i=0;i<B;++i)fd[i]=l+(r-l)/B*i;
fd[B]=r;
int mx=0;
for(int i=0;i<B;++i)mx=max(mx,fd[i+1]-fd[i]);
int pp=mx;
mx=3*mx+1;
while(mx&(mx-1))++mx;
int L=__builtin_ctz(mx);
getrev(L);
vector<int>vv;
for(int i=0;i<(1<<L);++i)vv.emplace_back(rev[i]);
vector<int>pt[B];
for(int i=0;i<B;++i){
for(int j=0;j<(1<<L);++j)a[j]=0;
for(int j=fd[i]-l;j<fd[i]-l+2*pp&&j<r;++j)a[j-fd[i]+l]=aa[j];
ntt(L,a,ap,1);
for(int j=0;j<(1<<L);++j)pt[i].emplace_back(ap[j]);
}
vector<int>tp[B];
for(int i=0;i<B;++i){
for(int k=0;k<(1<<L);++k)ap[k]=0;
for(int j=0;j<i;++j){
for(int k=0;k<(1<<L);++k)
ap[k]=(ap[k]+1ll*tp[j][k]*pt[i-j-1][k])%mod;
}
ntt(L,ap,a,-1);
for(int k=fd[i];k<fd[i+1];++k)
bb[k]=(bb[k]+a[k-fd[i]+(fd[1]-fd[0])])%mod;
solve(fd[i],fd[i+1]);
for(int k=0;k<(1<<L);++k)rev[k]=vv[k];
for(int k=0;k<(1<<L);++k){
a[k]=(k<fd[i+1]-fd[i]?bb[fd[i]+k]:0);
}
ntt(L,a,ap,1);
for(int k=0;k<(1<<L);++k)tp[i].emplace_back(ap[k]);
}
}
poly exp(poly a){
int n=a.size();
init(n);
for(int i=0;i<n;++i)aa[i]=1ll*i*a[i]%mod,bb[i]=0;
bb[0]=1;
for(int i=1;i<n;++i)bb[i]=(bb[i]+aa[i])%mod;
solve(1,n);
poly b;
for(int i=0;i<n;++i)b.emplace_back((bb[i]+mod)%mod);
return b;
}
int ans[500005],ka[500005];
int qiu(int z,int k){
k-=z;--z;
if(k<0)return 0;
return (C(z+2*k,k)-C(z+2*k,k-1)+mod)%mod;
}
int main(){
freopen("schrodingerstomb.in","r",stdin);
freopen("schrodingerstomb.out","w",stdout);
int n,x;
scanf("%d%d",&n,&x);
init(2*n);
int s=x,t=n-x+1;
poly z1(s+1),z2(t+1);
for(int i=1;i<=s;++i){
z1[i]=1ll*id[i-1]*qiu(i,s)%mod;
}
for(int i=1;i<=t;++i){
z2[i]=1ll*id[i-1]*qiu(i,t)%mod;
}
poly zz=multi({z1,z2});
for(int i=2;i<=n+1;++i){
int xs=1ll*di[i-2]*zz[i]%mod;
ans[i-1]=(ans[i-1]+xs)%mod;
}
for(int i=0;i<=n;++i){
ka[i]=(C(2*i,i)-C(2*i,i-1)+mod)%mod;
}
poly p1(s+1),p2(t+1);
for(int i=1;i<=s;++i)p1[i]=ka[i-1];
for(int i=1;i<=t;++i)p2[i]=ka[i-1];
poly pp=multi({p1,p2});
for(int i=2;i<=s+t;++i){
ans[n-i+3]=(ans[n-i+3]-1ll*ka[n-i+1]*pp[i]%mod+mod)%mod;
}
for(int i=2;i<=n;++i)ans[i]=(ans[i]+ans[i-1])%mod;
for(int i=1;i<=n;++i){
printf("%d\n",(ans[i]+mod)%mod);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Dangerous Syscalls
input:
5 2