QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#379094#6196. Minimum Element ProblemTx_LcyAC ✓275ms104792kbC++149.6kb2024-04-06 16:10:362024-04-06 16:10:36

Judging History

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

  • [2024-04-06 16:10:36]
  • 评测
  • 测评结果:AC
  • 用时:275ms
  • 内存:104792kb
  • [2024-04-06 16:10:36]
  • 提交

answer

//A tree without skin will surely die.
//A man without face will be alive.
#include<bits/stdc++.h>
using namespace std;
#define int long long
int const N=2e6+10;
int const mod=998244353;
typedef unsigned long long ull;typedef vector<int>vec;inline int add(int x,int y){return(x+y>=mod)?x+y-mod:x+y;}inline int dec(int x,int y){return(x-y<0)?x-y+mod:x-y;}inline void inc(int&x,int y){x=add(x,y);}inline void rec(int&x,int y){x=dec(x,y);}inline int ksm(int x,int y){int ret=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)ret=1ll*ret*x%mod;return ret;}namespace Prep{int Wn[N<<1],lg[N],p2,mx=1,r[N],tot;inline void init_poly(int n){int p=1;while(p<=n)p<<=1;for(int i=2;i<=p;++i)lg[i]=lg[i>>1]+1;for(int i=1;i<p;i<<=1){int wn=ksm(3,(mod-1)/(i<<1));Wn[++tot]=1;for(int j=1;j<i;++j)++tot,Wn[tot]=1ll*Wn[tot-1]*wn%mod;}}inline void init(int lim){int len=lg[lim]-1;for(int i=0;i<lim;++i)r[i]=(r[i>>1]>>1)|((i&1)<<len);}int iv[N],tp;inline void init_inv(int n){if(!tp){tp=2;iv[0]=iv[1]=1;}for(;tp<=n;++tp)iv[tp]=1ll*(mod-mod/tp)*iv[mod%tp]%mod;}}using namespace Prep;namespace Cipolla{int I,fl=0;mt19937 rnd(time(0));struct pt{int a,b;pt(int _a=0,int _b=0){a=_a;b=_b;}};inline pt operator*(pt x,pt y){pt ret;ret.a=add(1ll*x.a*y.a%mod,1ll*x.b*y.b%mod*I%mod);ret.b=add(1ll*x.a*y.b%mod,1ll*x.b*y.a%mod);return ret;}inline bool check(int x){return ksm(x,(mod-1)/2)==1;}inline int random(){return rnd()%mod;}inline pt qpow(pt a,int b){pt ret=pt(1,0);for(;b;a=a*a,b>>=1)if(b&1)ret=ret*a;return ret;}inline int cipolla(int n){if(!check(n))return 0;int a=random();while(!a||check(dec(1ll*a*a%mod,n)))a=random();I=dec(1ll*a*a%mod,n);int ans=qpow(pt(a,1),(mod+1)/2).a;return min(ans,(int)mod-ans);}}using namespace Cipolla;int ddddd=0;bool flag=0;namespace Poly{struct poly{vec v;inline poly(int w=0):v(1){v[0]=w;}inline poly(const vec&w):v(w){}inline int operator[](int x)const{return x>=v.size()?0:v[x];}inline int&operator[](int x){if(x>=v.size())v.resize(x+1);return v[x];}inline int size(){return v.size();}inline void resize(int x){v.resize(x);}inline void read(int n){v.resize(n);for(int i=0;i<n;++i)cin>>v[i];}inline void set(vector<int>u){v=u;}inline void print(int n)const{for(int i=0;i<n;++i)cout<<operator[](i)<<' ';cout<<'\n';}inline poly slice(int len)const{if(len<=v.size())return vec(v.begin(),v.begin()+len);vec ret(v);ret.resize(len);return ret;}inline poly operator*(const int&x)const{poly ret(v);for(int i=0;i<v.size();++i)ret[i]=1ll*ret[i]*x%mod;return ret;}inline poly operator-()const{poly ret(v);for(int i=0;i<v.size();++i)ret[i]=dec(0,ret[i]);return ret;}inline poly operator*(const poly&g)const;inline poly operator/(const poly&g)const;inline poly operator%(const poly&g)const;inline poly der()const{vec ret(v);for(int i=0;i<ret.size()-1;++i)ret[i]=1ll*ret[i+1]*(i+1)%mod;ret.pop_back();return ret;}inline poly jifen()const{vec ret(v);init_inv(ret.size());ret.push_back(0);for(int i=ret.size()-1;i;--i)ret[i]=1ll*ret[i-1]*iv[i]%mod;ret[0]=0;return ret;}inline poly rev()const{vec ret(v);reverse(ret.begin(),ret.end());return ret;}inline poly inv()const;inline poly div(const poly&FF)const;inline poly ln()const;inline poly exp()const;inline poly pow(int k)const;inline poly sqrt()const;inline poly mulT(const poly&g,int siz,int tp)const;};inline poly operator+(const poly&x,const poly&y){vec v(max(x.v.size(),y.v.size()));for(int i=0;i<v.size();++i)v[i]=add(x[i],y[i]);return v;}inline poly operator-(const poly&x,const poly&y){vec v(max(x.v.size(),y.v.size()));for(int i=0;i<v.size();++i)v[i]=dec(x[i],y[i]);return v;}ull fr[N];ull const Mod=998244353;inline void NTT(poly&f,int lim,int tp){for(int i=0;i<lim;++i)fr[i]=f[r[i]];for(int mid=1;mid<lim;mid<<=1){for(int len=mid<<1,l=0;l+len-1<lim;l+=len){for(int k=l;k<l+mid;++k){ull w1=fr[k],w2=fr[k+mid]*Wn[mid+k-l]%Mod;fr[k]=w1+w2;fr[k+mid]=w1+Mod-w2;}}}for(int i=0;i<lim;++i)fr[i]>=Mod?fr[i]%=Mod:0;if(!tp){reverse(fr+1,fr+lim);int iv=ksm(lim,mod-2);for(int i=0;i<lim;++i)fr[i]=fr[i]*iv%mod;}for(int i=0;i<lim;++i)f[i]=fr[i];}inline poly poly::operator*(const poly&G)const{poly f(v),g=G;int rec=f.size()+g.size()-1,d=max(f.size(),g.size());int len=lg[rec],lim=1<<len+1;init(lim);NTT(f,lim,1);NTT(g,lim,1);for(int i=0;i<lim;++i)f[i]=1ll*f[i]*g[i]%mod;NTT(f,lim,0);return f.slice(rec);}inline poly poly::inv()const{poly g,g0,d;g[0]=ksm(v[0],mod-2);for(int lim=2;(lim>>1)<v.size();lim<<=1){g0=g;d=slice(lim);init(lim);NTT(g0,lim,1);NTT(d,lim,1);for(int i=0;i<lim;++i)d[i]=1ll*g0[i]*d[i]%mod;NTT(d,lim,0);fill(d.v.begin(),d.v.begin()+(lim>>1),0);NTT(d,lim,1);for(int i=0;i<lim;++i)d[i]=1ll*d[i]*g0[i]%mod;NTT(d,lim,0);for(int i=lim>>1;i<lim;++i)g[i]=dec(g[i],d[i]);}return g.slice(v.size());}inline poly poly::div(const poly&FF)const{if(v.size()==1)return 1ll*v[0]*ksm(FF[0],mod-2)%mod;int len=lg[v.size()],lim=1<<len+1,nlim=lim>>1;poly F=FF,G0=FF.slice(nlim);G0=G0.inv();poly H0=slice(nlim),Q0;init(lim);NTT(G0,lim,1);NTT(H0,lim,1);for(int i=0;i<lim;++i)Q0[i]=1ll*G0[i]*H0[i]%mod;NTT(Q0,lim,0);Q0.resize(nlim);poly ret=Q0;NTT(Q0,lim,1);NTT(F,lim,1);for(int i=0;i<lim;++i)Q0[i]=1ll*Q0[i]*F[i]%mod;NTT(Q0,lim,0);fill(Q0.v.begin(),Q0.v.begin()+nlim,0);for(int i=nlim;i<lim&&i<v.size();++i)Q0[i]=dec(Q0[i],v[i]);NTT(Q0,lim,1);for(int i=0;i<lim;++i)Q0[i]=1ll*Q0[i]*G0[i]%mod;NTT(Q0,lim,0);for(int i=nlim;i<lim;++i)ret[i]=dec(ret[i],Q0[i]);return ret.slice(v.size());}inline poly poly::ln()const{return der().div(*this).jifen();}namespace EXP{const int logB=4;const int B=16;poly f,ret,g[30][B];inline void exp(int lim,int l,int r){if(r-l<=64){for(int i=l;i<r;++i){ret[i]=(!i)?1:1ll*ret[i]*iv[i]%mod;for(int j=i+1;j<r;++j)inc(ret[j],1ll*ret[i]*f[j-i]%mod);}return;}int k=(r-l)/B;poly bl[B];for(int i=0;i<B;++i)bl[i].resize(k<<1);int len=1<<lim-logB+1;for(int i=0;i<B;++i){if(i>0){init(len);NTT(bl[i],len,0);for(int j=0;j<k;++j)inc(ret[l+i*k+j],bl[i][j+k]);}exp(lim-logB,l+i*k,l+(i+1)*k);if(i<B-1){poly H;H.resize(k<<1);for(int j=0;j<k;++j)H[j]=ret[j+l+i*k];init(len);NTT(H,len,1);for(int j=i+1;j<B;++j)for(int t=0;t<(k<<1);++t)inc(bl[j][t],1ll*H[t]*g[lim][j-i-1][t]%mod);}}}inline void init_exp(){ret.resize(f.size());for(int i=0;i<f.size();++i)f[i]=1ll*f[i]*i%mod,ret[i]=0;int mx=lg[f.size()]+1;init_inv(1<<mx);for(int lim=mx;lim>=logB;lim-=logB){int bl=1<<(lim-logB),tot=0,ll=1<<(lim-logB+1);init(ll);for(int i=0;i<B-1;++i){g[lim][i].resize(bl<<1);for(int j=0;j<(bl<<1);++j)g[lim][i][j]=f[j+bl*i];NTT(g[lim][i],ll,1);}}}}inline poly poly::exp()const{EXP::f=*this;EXP::init_exp();EXP::exp(lg[v.size()]+1,0,1<<lg[v.size()]+1);return EXP::ret.slice(v.size());}inline poly poly::pow(int k)const{return((*this).ln()*k).exp();}inline poly poly::operator/(const poly&Q)const{if(v.size()<Q.v.size())return 0;int p=v.size()-Q.v.size()+1;poly fr=rev(),qr=Q.rev();fr.resize(p);qr.resize(p);return fr.div(qr).rev();}inline poly poly::operator%(const poly&Q)const{poly F(v);return(F-(Q*(F/Q))).slice(Q.v.size()-1);}inline poly poly::sqrt()const{poly g,h,gf,F1,F2,F3,f(v);g[0]=cipolla(operator[](0));h[0]=ksm(g[0],mod-2);gf[0]=g[0];gf[1]=g[0];int iv=(mod+1)/2;init(1);for(int lim=1;lim<v.size();lim<<=1){for(int i=0;i<lim;++i)F1[i]=1ll*gf[i]*gf[i]%mod;NTT(F1,lim,0);for(int i=0;i<lim;++i)F1[i+lim]=dec(F1[i],f[i]),F1[i]=0;int nlim=lim<<1;init(nlim);for(int i=lim;i<nlim;++i)rec(F1[i],f[i]);F2=h;F2.resize(lim);NTT(F1,nlim,1);NTT(F2,nlim,1);for(int i=0;i<nlim;++i)F1[i]=1ll*F1[i]*F2[i]%mod;NTT(F1,nlim,0);for(int i=lim;i<nlim;++i)g[i]=dec(0,1ll*F1[i]*iv%mod);if(nlim<v.size()){gf=g;NTT(gf,nlim,1);for(int i=0;i<nlim;++i)F3[i]=1ll*gf[i]*F2[i]%mod;NTT(F3,nlim,0);fill(F3.v.begin(),F3.v.begin()+lim,0);NTT(F3,nlim,1);for(int i=0;i<nlim;++i)F3[i]=1ll*F3[i]*F2[i]%mod;NTT(F3,nlim,0);for(int i=lim;i<nlim;++i)rec(h[i],F3[i]);}}return g.slice(v.size());}inline poly poly::mulT(const poly&G,int siz,int tp)const{poly f(v),g=G;if(f.size()<=100){poly ret;for(int i=0;i<f.size();++i){int fr=0;if(tp==1)fr=max(fr,i-(int)(f.size()-g.size()));for(int j=fr;j<=i&&j<g.size();++j)inc(ret[i-j],1ll*f[i]*g[j]%mod);}return ret;}int len=lg[f.size()*tp],lim=1<<len+1,gg=g.size();init(lim);reverse(g.v.begin(),g.v.end());NTT(f,lim,1);NTT(g,lim,1);for(int i=0;i<lim;++i)f[i]=1ll*f[i]*g[i]%mod;NTT(f,lim,0);return vec(f.v.begin()+gg-1,f.v.begin()+gg+siz-1);}}
using namespace Poly;
//remember to init_poly(多项式最高可能次数) 
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define all(x) (x).begin(),(x).end()
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define per(i,j,k) for (int i=j;i>=k;--i)
int fac[N],inv[N],ans[N],cdep[N],csiz[N],n,x;
inline int qpow(int a,int b){int r=1;while (b){if (b&1) r*=a,r%=mod;a*=a,a%=mod,b>>=1;}return r;}
inline int C(int n,int m){if (n<m) return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;}
inline int Ctl(int n){return C(2*n,n)*qpow(n+1,mod-2)%mod;}
inline int get(int x,int y){return C(2*x-y-1,x-y)*y%mod*qpow(x,mod-2)%mod;}
inline void get_cdep(){
    vector<int>A,B;init_poly(n);
    rep(i,0,x-1) A.push_back(get(x,i+1)*inv[i]%mod);
    rep(i,0,n-x) B.push_back(get(n-x+1,i+1)*inv[i]%mod);
    poly a(A),b(B),c=a*b;
    rep(i,1,n) cdep[i]=c[i-1]*fac[i-1]%mod;
}
inline void get_csiz(){
    vector<int>A,B;
    rep(i,0,x-1) A.push_back(Ctl(i));
    rep(i,0,n-x) B.push_back(Ctl(i));
    poly a(A),b(B),c=a*b;
    rep(i,1,n) csiz[i]=c[i-1]*Ctl(n-i)%mod;
}
inline void solve(){
    cin>>n>>x;
    ans[1]=Ctl(x-1)*Ctl(n-x)%mod;
    get_cdep(),get_csiz();
    rep(i,2,n) ans[i]=(ans[i-1]+mod-csiz[n+1-(i-1)]+cdep[i])%mod;
    rep(i,1,n) cout<<ans[i]<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    fac[0]=1;
    rep(i,1,N-1) fac[i]=fac[i-1]*i%mod;
    inv[N-1]=qpow(fac[N-1],mod-2);
    per(i,N-2,0) inv[i]=inv[i+1]*(i+1)%mod;
    int t=1;
    // cin>>t;
    while (t--) solve();
    cerr<<"Time: "<<(double)clock()/CLOCKS_PER_SEC<<" s\n";
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 18ms
memory: 45080kb

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: 11ms
memory: 47128kb

input:

10 5

output:

588
1176
2716
4942
7407
9101
9636
9167
7596
4862

result:

ok 10 numbers

Test #3:

score: 0
Accepted
time: 251ms
memory: 99976kb

input:

500000 1

output:

752527092
752527092
356448531
118361535
80175537
877228690
209078427
453506156
121930551
870611121
548521681
932222500
877888556
339507693
727002572
260384266
821810888
163642149
575555577
658980933
234580785
344625334
385680534
342084167
446322884
625631289
815673835
143033406
834945846
697825903
4...

result:

ok 500000 numbers

Test #4:

score: 0
Accepted
time: 263ms
memory: 103764kb

input:

500000 233333

output:

138363804
276727608
913261867
200515458
98174965
678246093
927769485
382014114
279795571
189839383
793297320
457630387
247544984
428942831
277533813
88681322
624390630
921439292
168596569
954739113
979085346
687234058
393708687
497103558
286734849
179380498
473893314
393946995
822316346
485246191
92...

result:

ok 500000 numbers

Test #5:

score: 0
Accepted
time: 275ms
memory: 100960kb

input:

499999 114514

output:

341241717
682483434
394686579
953386037
677673958
904444378
480913543
895868144
176048066
234816259
736395238
354978365
6204402
236101366
864038383
804451311
473145556
770789285
76089413
836469366
829878019
448657883
22407787
956778740
776897403
375485911
804351816
370141803
717651675
394600139
5347...

result:

ok 499999 numbers

Test #6:

score: 0
Accepted
time: 247ms
memory: 99124kb

input:

466047 378542

output:

316308363
632616726
625328547
548058021
467831491
412249015
562771998
508534419
702318310
663161493
71297932
569391807
528363739
577103129
75851585
281129409
253324073
555237826
523497876
9329476
595651189
113409967
689415978
758768684
461344695
271342234
922636023
896745521
753799440
454281460
8498...

result:

ok 466047 numbers

Test #7:

score: 0
Accepted
time: 271ms
memory: 104792kb

input:

497799 442442

output:

540969780
83695207
921588610
541249578
212472530
147071951
843635401
456883686
551483676
319785278
129435321
398101925
294235139
653012857
781822424
891809319
10513719
612056872
376014502
828906445
950887259
230704126
807999128
290793371
246195343
411365869
934684624
509617751
998233677
996675668
34...

result:

ok 497799 numbers

Test #8:

score: 0
Accepted
time: 254ms
memory: 104176kb

input:

466753 419673

output:

597092992
195941631
35282209
670914306
416494384
664725208
464875750
709887141
730156891
961628244
14612612
245382798
764095090
474984466
17211503
243033312
636210322
917825652
374184874
65295028
974019379
560137128
569803312
547566684
460710417
911778842
953566231
318861526
622281663
898785393
3283...

result:

ok 466753 numbers

Test #9:

score: 0
Accepted
time: 252ms
memory: 97248kb

input:

467106 241969

output:

604311529
210378705
653856122
53407242
877563744
89862040
632233611
996021679
619177538
520557738
575283710
211917888
496972337
34709258
595060683
625661602
15046904
770633381
497290822
218631007
239931201
23236894
578432596
428901738
504948079
877566897
998082459
443758906
296654733
59363332
898295...

result:

ok 467106 numbers

Test #10:

score: 0
Accepted
time: 252ms
memory: 97292kb

input:

486061 115034

output:

331165032
662330064
25375445
506130213
871487194
485340585
595821481
719592290
466027466
441948467
508478606
8931379
859094189
505253385
804451132
52690798
925691683
108838807
681231074
644121957
911203033
190055176
696385690
936750672
753723350
200690758
840546153
39260738
242234801
958678150
92648...

result:

ok 486061 numbers

Test #11:

score: 0
Accepted
time: 251ms
memory: 97344kb

input:

467812 448354

output:

900296606
802348859
920449046
342092877
15903803
315457190
610050785
677368557
827898162
850348006
918145269
100413429
286141122
723506730
444503335
498737569
412741085
55182144
622915390
145398304
361786018
453817918
325379444
279159566
612579035
555703010
284796267
31457982
547199941
167269220
917...

result:

ok 467812 numbers

Test #12:

score: 0
Accepted
time: 252ms
memory: 104636kb

input:

486767 465253

output:

896140171
794035989
38457645
667018451
121077123
988018258
454886247
148667810
782822242
208886808
641186382
664983537
135609621
929099937
781283105
673597413
898333512
533372308
349436050
608656262
229842701
591579717
102946839
732166129
415428398
269284759
811402014
588459181
448836208
30635772
14...

result:

ok 486767 numbers

Test #13:

score: 0
Accepted
time: 264ms
memory: 96220kb

input:

455721 231993

output:

861554085
724863817
681201785
82707070
329170451
815432452
480078531
960748236
199985657
265729483
43600900
600505341
942806449
749230414
634217227
690651435
92408500
559745153
336853395
259055628
322977700
244145248
806934059
60422830
229138080
978023704
52573139
622964643
298105514
878856237
79116...

result:

ok 455721 numbers

Test #14:

score: 0
Accepted
time: 245ms
memory: 98532kb

input:

456074 166647

output:

550779515
103314677
680704969
104574508
421361420
116643622
662147096
817326397
947520551
180619995
27083749
470585529
491549290
514402213
308761194
350599064
923257834
308640880
614091608
114961735
934141925
413458402
982181885
925717354
288272850
10675839
578069676
657318380
431067097
927121546
45...

result:

ok 456074 numbers

Test #15:

score: 0
Accepted
time: 258ms
memory: 99612kb

input:

455455 165608

output:

818811474
639378595
559603642
505656460
732593061
518746340
763553035
619494907
724183639
517533699
565002043
469308457
942905250
972176896
126587792
234342559
715415951
639986417
796466894
23149560
432288560
256012618
37970347
784640990
338731371
397938827
514010733
565833174
65243657
565593692
685...

result:

ok 455455 numbers