QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#772611 | #9254. Random Variables | daduoli | AC ✓ | 254ms | 11736kb | C++14 | 1.1kb | 2024-11-22 20:43:51 | 2024-11-22 20:44:05 |
Judging History
answer
#include<bits/stdc++.h>
#define Yzl unsigned long long
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
#define lob lower_bound
#define pb emplace_back
typedef long long LL;
using namespace std;
const Yzl Lty=20120712;
const int MAXN=1010;
int P,n,m;
int f[MAXN][MAXN],C[MAXN][MAXN];
LL fad(LL x,LL y) {
return (x+y>=P?x+y-P:x+y);
}
LL ksm(LL x,LL y) { LL ret=1;
while(y) {
if(y&1) ret=ret*x%P;
x=x*x%P; y>>=1;
} return ret;
}
void vmain() {
scanf("%d%d",&n,&m); C[0][0]=1;
for(int i=1;i<=n;++i) {
C[i][0]=C[i][i]=1;
for(int j=1;j<i;++j) C[i][j]=fad(C[i-1][j-1],C[i-1][j]);
} LL ans=ksm(m,n)*n%P;
for(int k=1;k<n;++k) { int mx=min(n/(k+1),m);
for(int i=0;i<=n;++i) for(int j=0;j<=mx;++j) f[i][j]=0;
for(int i=0;i<=mx;++i) f[0][i]=1;
for(int i=1;i<=n;++i) {
mx=min((n-i)/(k+1),m);
for(int j=0;j<=mx;++j) {
f[i][j]=f[i-1][j];
if(i>=k+1) f[i][j]=fad(f[i][j],P-(LL)f[i-k-1][j+1]*C[i-1][k]%P);
f[i][j]=(LL)f[i][j]*(m-j)%P;
}
} ans=fad(ans,P-f[n][0]);
} printf("%lld\n",ans);
}
int main () {
int T=1; scanf("%d%d",&T,&P); while(T--) vmain();
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5928kb
input:
3 123456789 3 2 5 5 7 7
output:
18 7145 2066323
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 5872kb
input:
100 2 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 2...
output:
1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0
result:
ok 100 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 6004kb
input:
100 3 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 2...
output:
1 2 0 1 2 0 1 2 0 1 2 0 0 2 0 0 2 0 0 2 0 0 0 0 0 0 0 0 0 0 1 2 0 1 2 0 1 2 0 1 2 2 0 2 2 0 2 2 0 2 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 2 2 0 2 2 0 2 2 0 2 0 0 0 0 0 0 0 0 0 0 1 2 0 1 2 0 1 2 0 1
result:
ok 100 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 5952kb
input:
100 4 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 2...
output:
1 2 3 0 1 2 3 0 1 2 2 2 0 0 2 2 0 0 2 2 3 2 3 0 3 2 3 0 3 2 0 0 0 0 0 0 0 0 0 0 1 2 3 0 1 2 3 0 1 2 2 0 2 0 2 0 2 0 2 0 3 0 3 0 3 0 3 0 3 0 0 0 0 0 0 0 0 0 0 0 1 2 3 0 1 2 3 0 1 2 2 0 2 0 2 0 2 0 2 0
result:
ok 100 lines
Test #5:
score: 0
Accepted
time: 1ms
memory: 5872kb
input:
100 5 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 2...
output:
1 2 3 4 0 1 2 3 4 0 2 1 2 0 0 2 1 2 0 0 3 3 1 3 0 3 3 1 3 0 4 4 2 4 0 4 4 2 4 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 0 1 2 3 4 0 2 3 3 2 0 2 3 3 2 0 3 4 1 2 0 3 4 1 2 0 4 4 4 4 0 4 4 4 4 0 0 0 0 0 0 0 0 0 0 0
result:
ok 100 lines
Test #6:
score: 0
Accepted
time: 1ms
memory: 5840kb
input:
100 6 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 2...
output:
1 2 3 4 5 0 1 2 3 4 2 0 0 2 0 0 2 0 0 2 3 0 3 0 3 0 3 0 3 0 4 2 0 4 2 0 4 2 0 4 5 2 3 2 5 0 5 2 3 2 0 0 0 0 0 0 0 0 0 0 1 0 3 4 3 0 1 0 3 4 2 2 0 2 2 0 2 2 0 2 3 0 3 0 3 0 3 0 3 0 4 2 0 4 2 0 4 2 0 4
result:
ok 100 lines
Test #7:
score: 0
Accepted
time: 1ms
memory: 5948kb
input:
100 7 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 2...
output:
1 2 3 4 5 6 0 1 2 3 2 6 5 6 2 0 0 2 6 5 3 4 2 3 6 3 0 3 4 2 4 2 3 5 2 5 0 4 2 3 5 5 3 6 5 4 0 5 5 3 6 0 6 1 1 6 0 6 0 6 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 0 1 2 3 2 1 4 4 1 2 0 2 1 4 3 3 4 3 4 4 0 3 3 4
result:
ok 100 lines
Test #8:
score: 0
Accepted
time: 1ms
memory: 5844kb
input:
100 8 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 2...
output:
1 2 3 4 5 6 7 0 1 2 2 6 4 4 6 2 0 0 2 6 3 2 3 4 3 6 3 0 3 2 4 4 0 0 4 4 0 0 4 4 5 6 3 4 1 2 7 0 5 6 6 4 6 0 6 4 6 0 6 4 7 4 3 0 7 4 3 0 7 4 0 0 0 0 0 0 0 0 0 0 1 6 3 4 5 2 7 0 1 6 2 4 6 0 2 4 6 0 2 4
result:
ok 100 lines
Test #9:
score: 0
Accepted
time: 1ms
memory: 5932kb
input:
100 9 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 2...
output:
1 2 3 4 5 6 7 8 0 1 2 6 3 2 3 6 2 0 0 2 3 0 6 0 6 3 6 3 0 3 4 8 3 4 5 6 4 2 0 4 5 2 0 2 8 0 8 5 0 5 6 0 0 6 0 0 6 0 0 6 7 3 6 1 3 3 4 3 0 7 8 8 6 5 8 3 2 8 0 8 0 0 0 0 0 0 0 0 0 0 1 8 3 4 2 6 7 5 0 1
result:
ok 100 lines
Test #10:
score: 0
Accepted
time: 1ms
memory: 7976kb
input:
100 10 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 ...
output:
1 2 3 4 5 6 7 8 9 0 2 6 2 0 0 2 6 2 0 0 3 8 1 8 5 8 3 6 3 0 4 4 2 4 0 4 4 2 4 0 5 0 5 0 5 0 5 0 5 0 6 2 8 4 0 6 2 8 4 0 7 8 3 2 5 2 3 8 7 0 8 4 6 2 0 8 4 6 2 0 9 4 9 4 5 4 9 4 9 0 0 0 0 0 0 0 0 0 0 0
result:
ok 100 lines
Test #11:
score: 0
Accepted
time: 1ms
memory: 6000kb
input:
100 11 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 ...
output:
1 2 3 4 5 6 7 8 9 10 2 6 1 9 8 9 1 6 2 0 3 7 7 9 8 10 10 3 6 3 4 0 5 5 10 10 8 9 9 6 5 0 4 10 6 7 10 4 2 7 6 10 4 5 3 2 0 7 2 5 7 5 2 8 6 1 6 0 3 6 8 6 6 3 2 4 8 3 6 9 9 8 10 2 8 6 10 9 3 1 10 0 4 3 0 6 0 7 4 9
result:
ok 100 lines
Test #12:
score: 0
Accepted
time: 99ms
memory: 11440kb
input:
10 972033073 576 523187654 758 588616188 30 532959085 476 481773028 573 76725430 520 142462406 865 820120297 687 526533288 913 38106557 67 924529654
output:
259748390 909910217 708973357 300073565 463921261 889897372 587262932 255642402 868975954 14589849
result:
ok 10 lines
Test #13:
score: 0
Accepted
time: 121ms
memory: 11736kb
input:
10 922366485 846 278501607 683 609355362 44 978777279 545 730718412 926 323835432 883 761846029 623 408215612 989 588832935 449 743830620 259 183431187
output:
461786112 672633342 164805246 547995105 9661617 154501063 370848893 402005970 886523490 435107511
result:
ok 10 lines
Test #14:
score: 0
Accepted
time: 119ms
memory: 11620kb
input:
10 13890975 949 837425969 667 981449995 991 564074312 501 604745038 593 640307170 128 408163542 80 976891742 930 710947599 852 333118419 250 333252788
output:
3898759 9290500 7087084 4913904 196250 1746549 9627740 8673120 10274253 10549775
result:
ok 10 lines
Test #15:
score: 0
Accepted
time: 68ms
memory: 11108kb
input:
10 105576445 649 937885257 141 713063090 253 716966251 845 330657011 347 664392407 810 50478969 389 530582574 228 199722046 85 256258366 605 3721959
output:
22721419 27962190 85541228 53950260 35288938 100176945 86409840 102331663 55591445 14790745
result:
ok 10 lines
Test #16:
score: 0
Accepted
time: 87ms
memory: 11500kb
input:
10 445185474 268 687201814 929 296077349 690 202741564 372 661889855 442 989604795 367 456833096 702 862601129 795 37538865 556 131444040 108 645857776
output:
39577672 390323147 423333756 49417686 12978114 278291170 60346062 410583855 68429394 296833176
result:
ok 10 lines
Test #17:
score: 0
Accepted
time: 119ms
memory: 11584kb
input:
10 265384486 870 503808438 959 733458117 126 226376632 979 205878607 747 270352323 339 384431347 373 659485098 597 832514575 832 906898547 12 869891031
output:
54820154 83262107 48675762 32938269 169458409 153632065 105152812 48645927 29870948 83831862
result:
ok 10 lines
Test #18:
score: 0
Accepted
time: 80ms
memory: 11300kb
input:
10 869896294 256 326197921 496 115501273 861 238744067 581 600444623 619 536213251 89 898877607 136 353575223 860 349472278 491 770026371 668 622723560
output:
678111040 344947200 90686837 157367547 295943299 25262829 81930384 532341712 23048077 475131428
result:
ok 10 lines
Test #19:
score: 0
Accepted
time: 144ms
memory: 11672kb
input:
10 692092859 831 647975618 792 737778459 392 768554014 854 612888229 31 148093584 793 559010229 970 237393805 339 914914862 831 979073722 988 738224088
output:
324659472 16793498 421391172 416475848 59704753 347151224 415078841 680610884 397373492 296521551
result:
ok 10 lines
Test #20:
score: 0
Accepted
time: 57ms
memory: 11652kb
input:
10 827165684 577 720722656 383 778750361 951 59165685 502 993162103 589 166261195 500 816688874 40 625075150 331 160531509 394 578798823 181 710984062
output:
736529364 199088527 528654835 586634074 442300715 383600380 707706396 763397655 534310310 338272096
result:
ok 10 lines
Test #21:
score: 0
Accepted
time: 67ms
memory: 11708kb
input:
10 691312083 185 445519030 93 44970277 951 662144708 252 766000017 83 911805458 424 816227326 770 136026896 354 763387805 247 458147285 747 14566368
output:
411209183 132362175 110569626 664410537 241484162 480388660 264805387 294178848 147876955 371900799
result:
ok 10 lines
Test #22:
score: 0
Accepted
time: 254ms
memory: 11736kb
input:
10 691312083 1000 445519030 1000 44970277 1000 662144708 1000 766000017 1000 911805458 1000 816227326 1000 136026896 1000 763387805 1000 458147285 747 14566368
output:
365043118 14826361 571573673 63977538 484010015 499398766 433242788 43269113 412491407 371900799
result:
ok 10 lines
Extra Test:
score: 0
Extra Test Passed