QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#814274 | #1414. Mascots | modwwe | 100 ✓ | 90ms | 69796kb | C++23 | 2.9kb | 2024-12-14 16:27:32 | 2024-12-14 16:27:37 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1<<k)
#define mp make_pair
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
inline int scan()
{
char c = getchar_unlocked();
int x = 0;
while (c < '0' || c > '9')
{
c = getchar_unlocked();
}
while (c >= '0' && c <= '9')
{
x = (x << 1) + (x << 3) + c - '0';
c = getchar_unlocked();
}
return x;
}
void phongbeo();
const int inf = 1e18;
const ll mod2 = 1e9+7;
const int mod1 = 998244353;
const ll base=67;
int add(int x,int y)
{
if(x+y>=mod2) x-=mod2;
if(x+y<0)x+=mod2;
return x+y;
}
struct icd
{
long double a;
int b;
};
struct ib
{
int a;
int b;
};
struct ic
{
int a, b, c;
};
struct id
{
int a, b, c, d;
};
struct ie
{
int a, b, c, d, e;
};
int n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int i, s10, s12,k1,k2,k3,s11,lim,w,l,r ;
int kk;
int el = 19;
main()
{
if(fopen(task".inp","r"))
{
fin(task);
fou(task);
}
NHP
/// cin>>s1;
// modwwe
phongbeo();
// checktime
}
int dp[3001][3001];
int fac[6001];
int invf[6001];
int ipow(int x,int y)
{
if(y==0) return 1;
int res=ipow(x,y/2);
res=res*res%mod2;
if(y%2==1) res=res*x%mod2;
return res;
}
int rmin,rmax=0,cmin,cmax=0;
void phongbeo()
{
cin>>n>>m;
cin>>k;
invf[0]=1;
fac[0]=1;
for(int i=1; i<=6000; i++)
fac[i]=fac[i-1]*i%mod2,
invf[i]=ipow(fac[i],mod2-2);
rmin=n+1;
cmin=m+1;
for(int i=1; i<=k; i++)
{
cin>>l>>r;
rmin=min(rmin,l);
rmax=max(rmax,l);
cmin=min(cmin,r);
cmax=max(cmax,r);
}
s6=(rmax-rmin+1)*(cmax-cmin+1);
s6-=k;
s5=1;
for(int i=1; i<=s6; i++)
s5=s5*i%mod2;
s6=s5;
s2=n-rmax+rmin-1;
s4=fac[s2]*invf[n-rmax]%mod2*invf[rmin-1]%mod2;
s3=m-cmax+cmin-1;
s4=s4*(fac[s3]*invf[m-cmax]%mod2*invf[cmin-1]%mod2)%mod2;
dp[0][0]=1;
s4=s4*s6%mod2;
for(int i=0; i<=s2; i++)
{
for(int j=1; j<=s3; j++)
dp[i][j]=add(dp[i][j],dp[i][j-1]*fac[rmax-rmin+1+i]%mod2);
if(i!=s2)
{
for(int j=0; j<=s3; j++)
dp[i+1][j]=add(dp[i+1][j],dp[i][j]*fac[cmax-cmin+j+1]%mod2);
}
}
cout<<dp[s2][s3]*s4%mod2;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 3688kb
input:
2 3 1 2 1
output:
14
result:
ok single line: '14'
Test #2:
score: 10
Accepted
time: 1ms
memory: 3664kb
input:
2 3 3 1 3 2 3 1 2
output:
2
result:
ok single line: '2'
Test #3:
score: 10
Accepted
time: 0ms
memory: 3748kb
input:
3 3 7 1 3 1 2 1 1 2 1 3 2 2 3 3 1
output:
2
result:
ok single line: '2'
Test #4:
score: 10
Accepted
time: 1ms
memory: 3684kb
input:
3 2 2 1 2 3 1
output:
24
result:
ok single line: '24'
Test #5:
score: 10
Accepted
time: 1ms
memory: 3668kb
input:
3 3 8 2 2 3 2 2 3 2 1 1 1 3 1 3 3 1 3
output:
1
result:
ok single line: '1'
Test #6:
score: 10
Accepted
time: 2ms
memory: 5748kb
input:
3 3 3 2 2 2 3 3 3
output:
24
result:
ok single line: '24'
Subtask #2:
score: 30
Accepted
Test #7:
score: 30
Accepted
time: 1ms
memory: 3804kb
input:
8 9 35 3 3 2 6 2 8 2 5 4 2 4 5 6 6 7 8 6 2 4 8 4 3 5 3 3 2 3 4 5 2 6 4 3 7 4 4 7 2 7 6 2 4 5 5 4 7 3 8 2 2 7 7 6 5 6 3 5 7 2 3 7 3 6 8 5 6 3 6 3 5
output:
575694721
result:
ok single line: '575694721'
Test #8:
score: 30
Accepted
time: 2ms
memory: 5756kb
input:
15 15 3 10 11 15 15 8 6
output:
584921510
result:
ok single line: '584921510'
Test #9:
score: 30
Accepted
time: 1ms
memory: 3816kb
input:
20 20 300 3 10 4 17 11 12 3 6 3 13 5 11 14 8 3 9 12 16 6 17 12 10 17 6 3 4 18 8 3 11 11 5 9 10 17 13 17 8 8 9 17 16 14 7 14 10 17 17 18 15 15 10 4 11 14 14 13 15 9 9 2 8 10 3 10 18 16 16 12 8 17 7 7 3 8 18 2 7 13 5 10 14 9 4 15 14 18 12 2 11 16 5 14 16 17 15 14 17 13 4 5 5 16 12 15 17 7 18 6 18 10 7...
output:
757097935
result:
ok single line: '757097935'
Test #10:
score: 30
Accepted
time: 1ms
memory: 3852kb
input:
20 20 49 9 14 9 10 6 9 5 14 10 11 10 10 10 12 9 11 8 10 6 10 11 14 10 8 7 12 8 11 10 9 5 13 8 9 10 14 9 12 6 13 6 12 11 13 11 12 7 13 9 13 7 8 5 10 5 9 8 13 5 11 7 10 11 10 5 8 6 8 8 12 9 8 11 8 6 14 7 14 7 9 10 13 6 11 8 8 5 12 9 9 11 11 7 11 11 9 8 14
output:
105784694
result:
ok single line: '105784694'
Test #11:
score: 30
Accepted
time: 1ms
memory: 3812kb
input:
17 21 1 13 10
output:
902780599
result:
ok single line: '902780599'
Test #12:
score: 30
Accepted
time: 1ms
memory: 3744kb
input:
24 29 400 6 12 2 25 16 11 12 15 13 16 15 10 11 8 15 14 4 10 10 7 12 12 19 28 22 26 7 7 19 27 12 21 8 29 10 18 2 14 8 9 9 20 13 12 17 14 19 17 8 14 4 14 8 7 4 28 13 28 14 9 22 12 21 15 11 28 9 11 19 26 16 18 15 17 21 23 16 29 17 17 3 25 2 19 21 21 16 12 23 12 5 19 21 16 20 21 6 15 13 18 21 27 13 11 1...
output:
833382390
result:
ok single line: '833382390'
Test #13:
score: 30
Accepted
time: 1ms
memory: 3732kb
input:
35 35 450 15 5 25 20 10 4 30 14 5 20 12 21 1 22 7 24 10 2 14 19 19 23 20 3 2 1 26 15 17 19 9 27 29 26 24 1 30 22 14 4 24 27 19 18 30 4 22 14 32 14 16 1 6 9 18 25 6 20 9 25 27 8 26 22 24 18 11 15 12 29 27 22 18 9 20 16 6 16 20 10 18 8 10 21 31 19 6 11 13 12 6 3 10 17 27 4 18 28 27 24 23 25 25 23 17 1...
output:
574120149
result:
ok single line: '574120149'
Test #14:
score: 30
Accepted
time: 0ms
memory: 3756kb
input:
35 35 1000 15 26 1 11 32 20 18 16 10 14 3 34 22 6 14 27 13 20 35 4 27 20 11 5 24 7 28 20 32 19 32 31 20 20 7 30 31 22 23 17 34 9 15 24 17 28 31 27 6 6 30 10 29 35 19 7 28 27 34 19 16 6 32 22 31 32 25 12 21 33 1 28 19 17 7 25 18 13 7 33 16 24 1 9 32 2 22 5 28 17 13 18 32 35 10 8 33 34 4 3 11 19 35 25...
output:
367193638
result:
ok single line: '367193638'
Test #15:
score: 30
Accepted
time: 0ms
memory: 3888kb
input:
50 50 30 8 20 8 34 8 35 8 32 8 38 8 22 8 31 8 23 8 14 8 41 8 16 8 30 8 25 8 36 8 19 8 33 8 24 8 37 8 17 8 28 8 39 8 26 8 40 8 18 8 13 8 29 8 15 8 21 8 27 8 42
output:
165646979
result:
ok single line: '165646979'
Test #16:
score: 30
Accepted
time: 1ms
memory: 3772kb
input:
17 48 160 11 30 14 28 10 38 11 26 14 30 14 16 14 13 12 34 10 35 13 12 10 25 14 22 13 15 12 16 12 13 14 14 12 27 10 19 10 20 10 21 13 27 11 35 13 29 9 24 14 12 9 19 11 22 11 36 12 19 11 25 13 31 12 36 10 34 11 15 10 29 12 25 10 33 12 26 9 26 9 12 13 17 12 28 11 16 14 37 12 12 13 14 14 17 14 18 12 30 ...
output:
485007512
result:
ok single line: '485007512'
Test #17:
score: 30
Accepted
time: 2ms
memory: 3792kb
input:
50 50 1500 13 15 10 30 10 16 39 15 28 8 38 17 16 25 24 14 24 7 11 21 20 5 24 41 34 25 32 21 36 31 32 41 21 15 42 39 15 31 25 13 35 29 15 30 28 4 14 26 46 5 12 12 24 12 44 15 48 25 23 11 18 38 44 4 11 40 29 31 21 19 11 31 34 13 45 42 29 39 42 29 47 8 22 18 41 13 44 41 46 22 34 31 38 37 43 35 47 11 11...
output:
769479583
result:
ok single line: '769479583'
Test #18:
score: 30
Accepted
time: 1ms
memory: 3748kb
input:
17 17 67 5 16 10 6 15 5 16 15 15 14 10 11 2 5 15 15 14 16 4 16 12 5 4 6 5 6 8 4 10 3 6 16 7 2 6 6 16 14 8 14 8 5 7 15 14 15 16 4 10 7 2 8 16 6 2 12 14 5 2 14 3 6 3 15 16 7 11 12 8 3 15 12 12 15 10 4 16 16 6 10 10 15 7 11 10 5 8 12 13 5 16 5 2 4 11 16 15 16 14 14 11 5 16 12 3 11 5 10 7 6 12 11 12 12 ...
output:
590961692
result:
ok single line: '590961692'
Subtask #3:
score: 60
Accepted
Test #19:
score: 60
Accepted
time: 1ms
memory: 3744kb
input:
215 198 20 56 192 29 195 167 192 86 192 212 193 71 195 187 197 5 196 48 197 68 194 77 195 44 197 13 194 125 198 33 192 176 192 187 195 176 194 214 197 3 196
output:
227315483
result:
ok single line: '227315483'
Test #20:
score: 60
Accepted
time: 2ms
memory: 4296kb
input:
280 296 2000 102 166 210 134 68 154 115 118 155 164 112 108 174 126 50 128 165 162 220 155 120 109 213 159 61 111 118 102 50 108 127 168 89 127 144 121 81 118 76 148 165 152 195 165 201 134 87 158 113 109 208 158 134 134 70 108 230 148 223 99 116 133 185 108 186 145 196 118 41 121 76 154 138 146 227...
output:
940721058
result:
ok single line: '940721058'
Test #21:
score: 60
Accepted
time: 0ms
memory: 5188kb
input:
300 299 4875 202 100 168 19 212 18 195 44 215 54 204 15 196 44 179 21 179 36 205 20 200 91 197 36 186 23 193 35 208 90 186 50 215 53 215 26 182 30 164 102 205 26 209 92 193 54 172 75 209 51 208 61 175 33 206 99 187 102 183 26 165 92 183 28 167 14 187 34 214 24 196 47 177 79 211 57 172 12 165 16 167 ...
output:
951284541
result:
ok single line: '951284541'
Test #22:
score: 60
Accepted
time: 4ms
memory: 12828kb
input:
857 927 37 744 445 723 447 728 465 725 479 730 483 726 493 726 446 729 460 729 477 733 457 729 490 728 467 722 482 734 490 733 491 726 448 730 476 723 446 737 455 739 470 739 481 741 491 726 491 742 488 744 476 723 484 725 473 742 485 740 456 729 458 727 453 731 489 742 493 724 444 735 486 740 447 7...
output:
877526378
result:
ok single line: '877526378'
Test #23:
score: 60
Accepted
time: 4ms
memory: 11588kb
input:
818 999 314 257 788 331 798 343 811 215 802 284 823 225 823 229 803 312 782 330 819 328 802 257 814 271 770 264 778 216 816 325 800 261 818 250 804 277 783 331 784 321 779 302 778 270 820 338 798 284 816 340 769 254 794 340 779 279 795 343 813 223 796 307 787 344 820 286 770 303 821 334 799 332 821 ...
output:
839005010
result:
ok single line: '839005010'
Test #24:
score: 60
Accepted
time: 11ms
memory: 8964kb
input:
1000 1000 100000 733 356 761 352 701 481 637 412 707 514 748 538 416 293 413 294 666 520 345 518 622 542 647 424 773 548 532 334 518 399 585 454 676 310 606 461 427 323 603 488 765 515 688 365 701 455 417 480 545 525 754 259 645 467 536 381 500 398 591 405 712 425 694 422 544 392 562 521 371 345 417...
output:
345294452
result:
ok single line: '345294452'
Test #25:
score: 60
Accepted
time: 3ms
memory: 5316kb
input:
1218 1415 75 823 770 552 811 495 808 795 767 1165 577 184 597 958 524 574 705 855 328 668 333 636 326 513 757 1110 792 229 684 950 621 371 670 746 375 832 600 404 505 807 441 267 613 814 669 719 634 1156 527 902 660 663 564 854 704 740 438 642 618 215 332 1078 776 809 469 911 368 214 797 834 620 848...
output:
425502270
result:
ok single line: '425502270'
Test #26:
score: 60
Accepted
time: 2ms
memory: 3816kb
input:
2000 1997 4000 1801 1448 895 1447 254 1447 301 1447 763 1448 1711 1448 571 1448 125 1448 1284 1448 1111 1447 1656 1448 1239 1447 1757 1448 228 1447 1039 1448 893 1448 1050 1448 1044 1448 196 1447 1502 1448 1526 1448 1869 1447 1001 1448 690 1448 98 1448 691 1447 199 1447 1915 1448 1071 1447 1790 1448...
output:
749630370
result:
ok single line: '749630370'
Test #27:
score: 60
Accepted
time: 30ms
memory: 3800kb
input:
3000 3000 60000 1698 1584 658 2134 1978 1844 34 753 841 2088 2895 1128 1143 1412 2955 1184 2347 1742 2954 821 789 1380 1553 890 163 1900 278 2201 1855 2297 205 1089 1727 2091 2709 1287 2865 1671 1043 1229 1782 897 467 1265 1792 2461 7 1290 2554 1786 2179 2465 1256 708 664 918 1416 747 1084 820 1509 ...
output:
573912616
result:
ok single line: '573912616'
Test #28:
score: 60
Accepted
time: 90ms
memory: 69796kb
input:
2817 2677 1 546 544
output:
891418449
result:
ok single line: '891418449'
Test #29:
score: 60
Accepted
time: 60ms
memory: 48300kb
input:
2500 2991 1257 191 2657 108 2617 175 2532 356 2543 538 2799 181 2955 299 2684 209 2763 521 2719 574 2823 251 2630 211 2690 172 2640 536 2785 260 2901 589 2637 216 2805 75 2764 353 2592 561 2883 517 2666 165 2687 527 2725 288 2804 84 2958 70 2898 476 2631 87 2880 525 2648 586 2664 184 2800 95 2723 19...
output:
639838982
result:
ok single line: '639838982'
Test #30:
score: 60
Accepted
time: 36ms
memory: 3804kb
input:
2993 2659 75000 231 14 1624 1335 2047 698 1777 919 1741 1945 22 192 123 49 2711 2594 1160 1642 1498 1929 716 1651 2970 1081 2216 2567 1888 2025 290 2061 2021 481 891 1922 2062 1598 2489 60 1720 2063 2349 1661 30 1652 257 117 2120 686 1481 1202 2605 2119 398 254 2822 727 2139 1275 2533 544 729 1438 1...
output:
767441023
result:
ok single line: '767441023'
Test #31:
score: 60
Accepted
time: 5ms
memory: 5720kb
input:
800 807 5 680 327 170 246 491 687 455 289 317 330
output:
46985985
result:
ok single line: '46985985'
Test #32:
score: 60
Accepted
time: 38ms
memory: 3756kb
input:
3000 3000 3000 2437 529 2984 2200 1699 342 2890 2416 870 1396 2475 1922 727 1886 2244 1173 2221 315 959 2408 874 546 1586 2113 148 1576 2275 247 638 45 933 2882 2483 540 1214 2380 1213 797 133 34 1462 369 2821 2281 2637 1233 2506 431 2102 1697 270 590 2392 2648 1889 382 1694 2733 1137 137 1383 921 1...
output:
926798008
result:
ok single line: '926798008'
Test #33:
score: 60
Accepted
time: 82ms
memory: 69420kb
input:
2998 2999 80000 2084 1402 2003 1214 2092 1019 2164 1122 2127 1016 2033 1033 2030 1084 2062 1168 2084 1218 2030 1307 2137 1139 2143 1196 2095 1179 2005 1216 2019 1389 2087 1100 2048 1276 2149 1374 2116 1048 2093 1090 2058 1336 2058 1353 2165 1324 2125 1228 2030 1092 2164 1132 2074 1342 2134 1378 2097...
output:
972757545
result:
ok single line: '972757545'
Test #34:
score: 60
Accepted
time: 48ms
memory: 53216kb
input:
2181 2773 50 1111 1541 1105 1568 1065 1542 1092 1555 1117 1543 1076 1564 1110 1533 1097 1538 1107 1521 1104 1563 1118 1512 1093 1518 1086 1566 1105 1562 1057 1544 1117 1550 1110 1574 1051 1564 1115 1568 1111 1543 1102 1534 1101 1516 1055 1567 1116 1543 1091 1564 1082 1524 1094 1548 1067 1521 1063 15...
output:
467808813
result:
ok single line: '467808813'
Test #35:
score: 60
Accepted
time: 36ms
memory: 8168kb
input:
3000 3000 53200 1526 1768 1365 1941 2449 2628 2242 260 497 2421 333 1096 507 2441 2512 2588 220 2201 2533 284 508 2432 437 1813 445 1820 231 1070 2570 990 2509 600 1344 936 1488 1081 2507 304 2255 999 2548 2656 377 621 481 2191 2293 2227 2387 542 2303 2232 1311 1702 327 2230 1460 1020 1365 1764 302 ...
output:
695028042
result:
ok single line: '695028042'
Test #36:
score: 60
Accepted
time: 72ms
memory: 66324kb
input:
3000 3000 100000 1302 2304 1229 2163 1068 2341 1023 2188 1026 2371 1105 2425 1129 2398 1294 2371 1090 2422 1099 2308 1191 2457 1075 2437 1136 2229 1105 2263 1250 2186 1110 2281 1325 2263 1276 2246 1133 2151 1001 2205 1267 2378 1144 2363 1135 2349 1189 2430 1087 2366 1248 2444 1231 2443 1058 2277 101...
output:
618651546
result:
ok single line: '618651546'
Extra Test:
score: 0
Extra Test Passed