QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#359025#6196. Minimum Element ProblemschrodingerstomWA 236ms36484kbC++143.7kb2024-03-20 11:09:212024-03-20 11:09:22

Judging History

你现在查看的是最新测评结果

  • [2024-03-20 11:09:22]
  • 评测
  • 测评结果:WA
  • 用时:236ms
  • 内存:36484kb
  • [2024-03-20 11:09:21]
  • 提交

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;
}

详细

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'