QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#359025 | #6196. Minimum Element Problem | schrodingerstom | WA | 236ms | 36484kb | C++14 | 3.7kb | 2024-03-20 11:09:21 | 2024-03-20 11:09:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
bool memBeg;
template<typename T> void chkmin(T &x,T y) {if(x>y) x=y;}
template<typename T> void chkmax(T &x,T y) {if(x<y) x=y;}
constexpr int mod=998244353;
void inc(int &x,int y) {x+=y; x-=(x>=mod)*mod;}
void dec(int &x,int y) {x-=y; x+=(x<0)*mod;}
constexpr int add(int x,int y) {return (x+y>=mod)?x+y-mod:x+y;}
constexpr int sub(int x,int y) {return (x<y)?x-y+mod:x-y;}
constexpr int quick_pow(int x,int times) {
int ret=1;
for(;times;times>>=1,x=1ll*x*x%mod) {
if(times&1) ret=1ll*ret*x%mod;
}
return ret;
}
constexpr int maxn=1<<19|5;
int n,un,x,fac[maxn<<1],ifac[maxn<<1],inv[maxn],cat[maxn];
int binom(int x,int y) {
if(x<0||y<0||x<y) return 0;
return 1ll*fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
int csiz[maxn],cdep[maxn],f[maxn],g[maxn],h[maxn<<1],rev[maxn<<1],pwg[maxn<<1];
void ntt(int *coef,int tp) {
for(int i=0;i<(un<<1);i++) if(i<rev[i]) swap(coef[i],coef[rev[i]]);
for(int i=2;i<=(un<<1);i<<=1) {
for(int j=0;j<(un<<1);j+=i) {
for(int k=j;k<(i>>1|j);k++) {
int u=coef[k],v=1ll*pwg[i-k+j]*coef[i>>1|k]%mod;
coef[k]=add(u,v); coef[i>>1|k]=sub(u,v);
}
}
}
if(tp==-1) {
reverse(coef+1,coef+(un<<1));
int iv=quick_pow(un<<1,mod-2);
for(int i=0;i<(un<<1);i++) coef[i]=1ll*coef[i]*iv%mod;
}
}
void convolution() {
memset(h,0,sizeof(h));
ntt(f,1); ntt(g,1);
for(int i=0;i<(un<<1);i++) h[i]=1ll*f[i]*g[i]%mod;
ntt(h,-1);
// for(int i=0;i<=n;i++) {
// for(int j=0;j<=n;j++) {
// h[i+j]=(h[i+j]+1ll*f[i]*g[j])%mod;
// }
// }
}
void gsiz() {
for(int i=0;i<x;i++) f[i]=cat[i];
for(int i=0;i<=n-x;i++) g[i]=cat[i];
convolution();
for(int i=0;i<n;i++) {
csiz[i+1]=1ll*h[i]*cat[n-i-1]%mod;
// printf("csiz[i+1 = %d] = %d\n",i+1,csiz[i+1]);
}
}
int calc(int x,int y) {
// printf("calc(x = %d, y = %d) = %d\n",x,y,(int)(1ll*binom(2*x+y,x)*(y+1)%mod*inv[x+y+1]%mod));
return 1ll*binom(2*x+y,x)*(y+1)%mod*inv[x+y+1]%mod;
}
void gdep() {
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
for(int i=0;i<x;i++) f[i]=1ll*calc(x-i-1,i)*ifac[i]%mod;
for(int i=0;i<=n-x;i++) g[i]=1ll*calc(n-x+1-i-1,i)*ifac[i]%mod;
convolution();
for(int i=0;i<n;i++) {
cdep[i+1]=1ll*h[i]*fac[i]%mod;
// printf("cdep[i+1 = %d] = %d\n",i+1,cdep[i+1]);
}
// static int pdep[maxn];
// for(int i=1;i<=n;i++) pdep[i]=add(pdep[i-1],cdep[i]);
// for(int i=1;i<=n;i++) printf("pdep[i = %d] = %d\n",i,pdep[i]);
}
bool memEn;
void fl() {
freopen(".in","r",stdin);
freopen(".out","w",stdout);
}
int main() {
fprintf(stderr,"%.24lf\n",fabs(&memEn-&memBeg)/1024.0/1024.0);
// fl();
scanf("%d%d",&n,&x);
fac[0]=1;
for(int i=1;i<=2*n;i++) fac[i]=1ll*fac[i-1]*i%mod;
ifac[2*n]=quick_pow(fac[2*n],mod-2);
for(int i=2*n-1;i>=0;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
inv[1]=1;
for(int i=2;i<=n+1;i++) inv[i]=mod-1ll*(mod/i)*inv[mod%i]%mod;
for(int i=0;i<=n;i++) cat[i]=1ll*binom(2*i,i)*inv[i+1]%mod;
un=1;
while(n>=un) un<<=1;
for(int i=0;i<(un<<1);i++) rev[i]=rev[i>>1]>>1|((i&1)*un);
for(int i=1;i<=(un<<1);i<<=1) {
int rt=quick_pow(3,(mod-1)/i);
pwg[i]=1;
for(int j=i-1;j>(i>>1);j--) pwg[j]=1ll*pwg[j+1]*rt%mod;
}
gsiz(); gdep();
int ret=1ll*cat[x-1]*cat[n-x]%mod;
printf("%d\n",ret);
for(int i=2;i<=n;i++) {
dec(ret,csiz[n+1-(i-1)]);
inc(ret,cdep[i]);
printf("%d\n",ret);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 24396kb
input:
5 2
output:
5 10 16 20 14
result:
ok 5 number(s): "5 10 16 20 14"
Test #2:
score: 0
Accepted
time: 4ms
memory: 24336kb
input:
10 5
output:
588 1176 2716 4942 7407 9101 9636 9167 7596 4862
result:
ok 10 numbers
Test #3:
score: -100
Wrong Answer
time: 236ms
memory: 36484kb
input:
500000 1
output:
752527092 560298362 981416241 79466958 871128284 498643266 251196787 936655535 903590389 288710767 904180626 661601892 946592092 463175391 175923330 568689970 474114061 256544482 564121319 377604650 561504991 452831943 623786283 766866864 114439487 485349499 115773044 991448182 768858742 145197497 4...
result:
wrong answer 2nd numbers differ - expected: '752527092', found: '560298362'