QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#388351 | #5097. 小 P 爱学习 | _l_l_ | 100 ✓ | 275ms | 5620kb | C++14 | 1.5kb | 2024-04-13 14:55:19 | 2024-04-13 14:55:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1505, mod = 1000000007;
int qkpow(int a, int b) {
int ans = 1; for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) ans = 1ll * ans * a % mod; return ans;
}
int fact[MAXN * 100], invf[MAXN * 100];
void mul(int *F, int *G, int *H, int k) {
for (int i = 0; i <= k; i++) {
__int128 X = 0; for (int j = 0; j <= i; j++) X += 1ll * F[j] * G[i - j]; H[i] = X % ::mod;
}
}
int f[41][MAXN], f2[38][MAXN], ftmp[MAXN], g[1505];
int read() {
char ch; while ((ch = getchar()) <= ' '); int x = ch - '0';
while ((ch = getchar()) > ' ') x = 10 * x + ch - '0'; return x;
}
int main() {
int n = read(), m = read();
fact[0] = 1; for (int i = 1; i <= n * m; i++) fact[i] = 1ll * fact[i - 1] * i % mod;
invf[n * m] = qkpow(fact[n * m], mod - 2);
for (int i = n * m - 1; ~i; i--) invf[i] = 1ll * invf[i + 1] * (i + 1) % mod;
for (int i = 1; i <= n; i++) ftmp[i] = invf[i * m - 1];
f[0][0] = 1;
for (int i = 1; i <= 40; i++) mul(f[i - 1], ftmp, f[i], n);
f2[0][0] = 1; for (int i = 1; i <= 37; i++) mul(f2[i - 1], f[40], f2[i], n);
for (int i = 1; i <= n; i++) {
int i1 = i % 40, i2 = i / 40; __int128 X = 0;
for (int j = 0; j <= n; j++) X += 1ll * f[i1][j] * f2[i2][n - j];
ftmp[i] = X % mod * fact[n * m - i] % mod;
}
g[0] = 1; for (int i = 0; i < n * m; i++) {
int a = read(); for (int j = n; j; j--) g[j] = (g[j] + 1ll * g[j - 1] * a) % mod;
}
int A = 0; for (int i = 1; i <= n; i++) A = (A + 1ll * ftmp[i] * g[i]) % mod; printf("%d", A);
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 4092kb
input:
3 4 993987920 851664708 532496582 332334976 645105194 437392477 101400616 97233810 821968468 15736516 160047245 366079295
output:
856280467
result:
ok answer is 856280467
Test #2:
score: 0
Accepted
time: 0ms
memory: 4152kb
input:
2 2 410797770 6809338 472422778 989528224
output:
428410815
result:
ok answer is 428410815
Test #3:
score: 0
Accepted
time: 0ms
memory: 4124kb
input:
1 2 61861880 797258571
output:
859120451
result:
ok answer is 859120451
Test #4:
score: 0
Accepted
time: 0ms
memory: 4148kb
input:
4 4 345828253 333235310 877508155 268177944 892729462 591630803 103568022 189412379 473190308 606582845 39234531 676920516 526713342 584876596 477385922 911117054
output:
130539277
result:
ok answer is 130539277
Test #5:
score: 0
Accepted
time: 0ms
memory: 4144kb
input:
3 4 497837179 320032498 88408654 686869221 955729904 891421702 840622668 700545094 994455042 397227737 872911626 764923114
output:
444700147
result:
ok answer is 444700147
Subtask #2:
score: 20
Accepted
Test #6:
score: 20
Accepted
time: 50ms
memory: 4244kb
input:
1500 1 613884366 318223729 617843443 151365784 314748737 778479063 762692152 762329264 560579744 428619194 148701427 891734077 339222910 692588908 180829596 615884679 688697194 981930569 856072945 973079346 407508504 185723413 482150672 944412007 548582506 572572951 297202679 276708377 552007154 951...
output:
716155203
result:
ok answer is 716155203
Test #7:
score: 0
Accepted
time: 50ms
memory: 4200kb
input:
1500 1 203946163 790756155 31880785 670720617 578032803 978211419 545524799 831170430 315457214 749338870 938190926 540898693 117170175 508468198 195897869 709484408 168150734 28068910 476238051 310956365 503395574 743107920 510982871 175542616 164902400 496501356 853160049 134615547 571906411 30301...
output:
673014307
result:
ok answer is 673014307
Test #8:
score: 0
Accepted
time: 51ms
memory: 4240kb
input:
1500 1 84869614 166989354 747450885 318354182 468629235 310852979 837778150 431330542 629725556 461633318 144111853 780737550 448212230 156411054 529516696 532965288 832680007 171808740 578171819 138906067 646999869 577255724 520945848 191524210 279391236 118616133 475169973 656690767 921746491 9987...
output:
198503963
result:
ok answer is 198503963
Test #9:
score: 0
Accepted
time: 50ms
memory: 4240kb
input:
1499 1 653054925 109470906 390970530 717020107 646929995 899421577 656477148 115141158 124058719 903220561 887601227 113934280 646598227 504529205 978403334 635650813 901811669 184325048 298833048 186091439 832843285 538527614 73677668 381132501 123839498 905560988 920236941 52720461 219606200 25431...
output:
565990166
result:
ok answer is 565990166
Test #10:
score: 0
Accepted
time: 50ms
memory: 4188kb
input:
1497 1 726348046 512456833 173926091 538307623 418534968 683578224 30631565 693232361 653147127 421461401 806414082 850512423 756123873 289504683 545013209 173529651 842096476 390808284 208681427 719150123 742145616 983822793 273803111 726750786 437249415 689245884 935836777 828643432 623602409 9543...
output:
989909589
result:
ok answer is 989909589
Subtask #3:
score: 15
Accepted
Test #11:
score: 15
Accepted
time: 1ms
memory: 4092kb
input:
100 42 544703372 456304555 178333752 808160596 628160657 264931494 810502429 20342061 203372934 920107110 466566652 470361058 680819469 879463750 668822108 781685938 40434324 800845096 913025163 971899062 986502509 122277391 523016525 579121406 413351231 882719635 632511496 453222515 350376424 37340...
output:
294362854
result:
ok answer is 294362854
Test #12:
score: 0
Accepted
time: 1ms
memory: 4216kb
input:
97 59 145973910 732552393 914117835 636326358 532988879 196179567 449096913 200286449 506667245 88914184 492830989 803343479 13122314 48886910 534862927 644699801 503933079 941278210 33036562 876272065 549714414 389742796 374688355 231452136 599779397 484904334 248135616 948542731 160728483 2816193 ...
output:
721228563
result:
ok answer is 721228563
Test #13:
score: 0
Accepted
time: 1ms
memory: 4160kb
input:
99 59 444571227 161900255 89110577 169714115 776991748 824971463 908851901 268337880 462869856 454683572 822185757 973216894 405232289 191527196 795862154 667584286 308392866 232084022 504614099 478739234 594586478 749474676 797766274 320319898 319149100 290058426 962757156 912139730 20160702 188462...
output:
983531240
result:
ok answer is 983531240
Test #14:
score: 0
Accepted
time: 1ms
memory: 4120kb
input:
100 17 127726208 743186510 693807356 129341996 847353309 986727820 227581828 30107198 624732712 785392623 895901317 215392500 848256148 91831462 833336941 263672260 404087327 572759689 68793683 2258751 459646119 598649469 49812051 790767693 137657371 877850745 750437008 103998593 672511095 21664377 ...
output:
973454852
result:
ok answer is 973454852
Test #15:
score: 0
Accepted
time: 0ms
memory: 4092kb
input:
100 44 916977821 723866535 527359595 415345224 509506855 474435823 112078586 361401748 172754292 276958823 128414574 202782635 912901635 170565341 845911624 126396287 699823031 149990522 387682802 758147090 710226510 75546714 638828895 934577998 845452877 749856580 616177589 409883183 765921061 5571...
output:
322002052
result:
ok answer is 322002052
Subtask #4:
score: 15
Accepted
Test #16:
score: 15
Accepted
time: 19ms
memory: 4448kb
input:
499 60 136856769 47869549 264538291 600887500 271130365 503375271 979728502 928286478 295751844 413206031 143796624 712745939 41348750 488666164 725432432 529794914 703056452 573552365 225245406 620490759 715276073 987544150 759181034 939466746 354701446 228245827 301255190 24876250 452483821 837389...
output:
157452172
result:
ok answer is 157452172
Test #17:
score: 0
Accepted
time: 30ms
memory: 4824kb
input:
499 85 562504815 255672999 94213375 581989419 668252780 699439947 470769415 337257242 436738945 916095446 546338582 24140453 986721745 298544808 112135210 907077983 405657612 143175757 635084746 324229902 159444226 615642851 364901685 807496902 803666646 796388458 573970527 581301100 518026673 93105...
output:
863459749
result:
ok answer is 863459749
Test #18:
score: 0
Accepted
time: 21ms
memory: 4424kb
input:
497 52 373956199 137225116 20424558 536477262 843485046 451227012 109515126 433523669 768063267 403061499 103369894 261991426 402021873 943160061 547591500 298165577 146900397 561253339 156264966 262069281 953421485 722499759 746737615 901316823 885052966 112733367 965653479 386594166 820836448 9267...
output:
161808660
result:
ok answer is 161808660
Test #19:
score: 0
Accepted
time: 20ms
memory: 4680kb
input:
500 50 743161824 615281538 663329449 497918079 255222721 782255840 755940028 545653814 36784608 436526724 991094852 592804400 627623554 79144539 362952152 903859218 459903189 954746982 30747342 464085914 470619706 19054080 527329203 49915180 930069522 333109991 810180528 445041336 874820694 50164104...
output:
229954465
result:
ok answer is 229954465
Test #20:
score: 0
Accepted
time: 23ms
memory: 4408kb
input:
497 60 448190718 890454639 206471347 669578477 239579473 126928340 120275613 61090463 183990894 440482849 603625557 868274020 837836264 657748834 314340092 863454190 521419163 442375337 566902212 614013922 978386800 14809865 705249377 251489813 108909523 145752032 857765306 378898439 357521883 93417...
output:
88661419
result:
ok answer is 88661419
Subtask #5:
score: 40
Accepted
Test #21:
score: 40
Accepted
time: 274ms
memory: 5620kb
input:
1500 93 299567650 399978478 101776752 583392666 56762099 127237968 595272440 581887945 332400603 269986805 17840600 323055242 263161884 607605816 966029729 591250421 964262680 642691696 658567473 339363823 715151825 270553684 202478735 193930303 14517687 248178770 917823665 315265457 473654173 33965...
output:
430115808
result:
ok answer is 430115808
Test #22:
score: 0
Accepted
time: 77ms
memory: 4656kb
input:
1499 12 660494825 877936607 91506877 831322665 136908399 928019046 971973128 681066565 552033550 432150111 488568487 106655736 442097407 615898136 17894518 694722175 470714023 918735044 98932516 816953130 290866992 212047624 752949839 373384851 194547888 308664949 113355877 205206632 995062636 24178...
output:
104161302
result:
ok answer is 104161302
Test #23:
score: 0
Accepted
time: 272ms
memory: 5264kb
input:
1500 92 127937454 268440901 579541803 564185111 274901759 337738070 953758584 927526392 255344193 850952880 483356259 665637864 37747957 159411103 309876234 607684169 179162953 777039741 924722113 184291084 297764060 480721649 951163233 32808444 932260448 108335523 564809950 856274718 721492675 5866...
output:
387260607
result:
ok answer is 387260607
Test #24:
score: 0
Accepted
time: 85ms
memory: 4412kb
input:
1500 15 783725624 125184652 537073398 774810281 208424562 980975292 449347501 763970537 125405725 480391384 196349184 179300084 586167938 946913402 423321911 934437763 179442226 304315809 123940030 575360104 774053159 294295111 725054236 363800948 177354963 320870150 89028060 579197161 921582541 706...
output:
785571328
result:
ok answer is 785571328
Test #25:
score: 0
Accepted
time: 275ms
memory: 5348kb
input:
1499 93 183710114 427028785 964508133 430339035 849194835 642127719 515912896 874084019 543803856 504905539 875282251 959758498 35814806 445987236 487998313 654968450 332062519 772819040 264442568 202120522 599488101 302254946 979014454 645229372 227733822 797934040 412580383 124168414 535812955 822...
output:
350011353
result:
ok answer is 350011353