QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#359027 | #6196. Minimum Element Problem | schrodingerstom | AC ✓ | 237ms | 40004kb | C++14 | 3.7kb | 2024-03-20 11:10:33 | 2024-03-20 11:10:33 |
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<<1],g[maxn<<1],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: 16184kb
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: 6ms
memory: 16176kb
input:
10 5
output:
588 1176 2716 4942 7407 9101 9636 9167 7596 4862
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 222ms
memory: 40004kb
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: 214ms
memory: 39988kb
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: 228ms
memory: 39932kb
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: 215ms
memory: 38924kb
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: 237ms
memory: 39992kb
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: 222ms
memory: 38992kb
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: 216ms
memory: 38988kb
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: 220ms
memory: 39600kb
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: 233ms
memory: 38972kb
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: 224ms
memory: 39624kb
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: 212ms
memory: 38676kb
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: 218ms
memory: 38668kb
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: 225ms
memory: 38656kb
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