QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#814274#1414. Mascotsmodwwe100 ✓90ms69796kbC++232.9kb2024-12-14 16:27:322024-12-14 16:27:37

Judging History

This is the latest submission verdict.

  • [2024-12-14 16:27:37]
  • Judged
  • Verdict: 100
  • Time: 90ms
  • Memory: 69796kb
  • [2024-12-14 16:27:32]
  • Submitted

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;
}

詳細信息

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