UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214162#2693. NEQFilberte1001997ms32448kbC++111.2kb2024-11-15 21:07:182024-11-15 23:26:43

answer

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 2e6 + 100;
const int p = 1e9 + 7;
int Inv(int x){
    int a = x, b = p - 2, r = 1;
    while(b){ 
        if(b & 1) r = r * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return r;
}
int fc[N], ifc[N];
int C(int n, int m){return fc[n] * ifc[n - m] % p * ifc[m] % p;}
int A(int n, int m){return fc[n] * ifc[n - m] % p;}
int32_t main(){
    const int maxn = 2e6;
    ifc[0] = fc[0] = 1;
    for(int i = 1;i <= maxn;i++)
        fc[i] = fc[i - 1] * i % p;
    ifc[maxn] = Inv(fc[maxn]);
    for(int i = maxn - 1;i;i--)
        ifc[i] = ifc[i + 1] * (i + 1) % p;
    int cas;cin >> cas;while(cas--){
        int n, m;
        cin >> n >> m;
        if(n > m){
            cout << 0 << endl;
            continue;
        }
        int s = 0, al = A(m, n) * A(m, n) % p;
        for(int k = 1;k <= n;k++){
            int v = C(m, k) * C(n, k) % p * A(m - k, n - k) % p * A(m - k, n - k) % p * fc[k] % p;
            if(k & 1) s = (s + v < p) ? s + v : s + v - p; 
            else s = (s - v >= 0) ? s - v : s - v + p;
        }
        int ans = (al - s >= 0) ? al - s : al - s + p;
        cout << ans << endl;
    }
    return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 16ms
memory: 32448kb

input:

10
10 10
10 10
2 10
3 10
9 10
1 10
8 10
7 10
1 10
10 10

output:

306442892
306442892
6570
379440
736724304
90
748248938
605640347
90
306442892

result:

ok 10 lines

Test #2:

score: 5
Accepted
time: 20ms
memory: 32444kb

input:

10
5 10
1 10
8 10
3 10
4 10
7 10
5 10
8 10
10 10
9 10

output:

547011360
90
748248938
379440
16798320
605640347
547011360
748248938
306442892
736724304

result:

ok 10 lines

Test #3:

score: 5
Accepted
time: 30ms
memory: 32444kb

input:

10
10 10
3 10
1 10
2 10
9 10
10 10
2 10
4 10
3 10
3 10

output:

306442892
379440
90
6570
736724304
306442892
6570
16798320
379440
379440

result:

ok 10 lines

Test #4:

score: 5
Accepted
time: 20ms
memory: 32444kb

input:

10
10 10
1 10
6 10
8 10
1 10
7 10
2 10
8 10
5 10
2 10

output:

306442892
90
383431116
748248938
90
605640347
6570
748248938
547011360
6570

result:

ok 10 lines

Test #5:

score: 5
Accepted
time: 76ms
memory: 32444kb

input:

10
209948 325367
32718 415553
23204 942400
112174 378481
606851 967435
136404 1014128
219328 240497
...

output:

486730033
795980345
588390998
322722869
736567390
174281893
343240658
708767580
981228075
955026181

result:

ok 10 lines

Test #6:

score: 5
Accepted
time: 139ms
memory: 32448kb

input:

10
138556 734356
435301 1331052
987730 1772096
814036 824058
46984 404156
483366 1120849
343377 9489...

output:

810123408
527527355
295291222
377407525
822697639
116308692
933876933
252771944
856057953
587372477

result:

ok 10 lines

Test #7:

score: 5
Accepted
time: 125ms
memory: 32444kb

input:

10
3667 227437
960664 1136884
126289 1829473
242537 1330052
375909 872744
356898 531785
229031 14944...

output:

417049407
38483898
593092347
316699464
187641847
596221024
194161650
126658777
673242737
73402752

result:

ok 10 lines

Test #8:

score: 5
Accepted
time: 132ms
memory: 32444kb

input:

10
567322 1929060
1001468 1289434
163254 319786
698923 843859
740264 759489
203918 1063292
508483 79...

output:

314836082
746974053
608229865
554511124
369805304
855891511
123129673
162284806
937141157
971139034

result:

ok 10 lines

Test #9:

score: 5
Accepted
time: 108ms
memory: 32444kb

input:

10
1132589 1775386
207807 262123
63505 1358101
1428754 1798082
418855 455426
73850 272549
48576 1778...

output:

734925409
378494075
498064480
529399291
804298543
607462662
480459318
411695195
628362397
270696417

result:

ok 10 lines

Test #10:

score: 5
Accepted
time: 119ms
memory: 32448kb

input:

10
1695462 1939750
29235 1185790
194617 546134
337070 554401
768444 1892158
332841 882745
154636 920...

output:

201885598
258543350
667374757
391816851
13410307
878053433
101841373
436754179
397015928
212382591

result:

ok 10 lines

Test #11:

score: 5
Accepted
time: 143ms
memory: 32444kb

input:

10
674754 1159686
406921 960658
932058 1996799
48795 455853
554994 1113156
121831 1251202
1177109 15...

output:

989838431
904392731
877867959
7105452
164196532
769960402
148401341
747194327
809416881
493740494

result:

ok 10 lines

Test #12:

score: 5
Accepted
time: 139ms
memory: 32444kb

input:

10
701259 1332249
16908 633852
601124 1004557
581334 1216395
715566 1429189
862389 1656521
1345860 1...

output:

978526302
525661372
805224412
821434633
700225257
634654448
549902843
985657721
472322010
963718574

result:

ok 10 lines

Test #13:

score: 5
Accepted
time: 88ms
memory: 32444kb

input:

10
509226 1079784
65211 359751
304345 1114412
270468 1517516
177717 1461562
4559 1484183
291180 1856...

output:

377614455
347018883
65641
556529706
116219835
15376029
749860123
486123471
645667307
702445002

result:

ok 10 lines

Test #14:

score: 5
Accepted
time: 108ms
memory: 32444kb

input:

10
844547 1065326
12765 348551
197870 493940
891829 1952960
408481 766220
42263 225437
1177449 15681...

output:

264953803
493067429
29274680
124035569
179754190
472719747
889127140
181261557
862089491
654690115

result:

ok 10 lines

Test #15:

score: 5
Accepted
time: 144ms
memory: 32448kb

input:

10
62489 1977001
1570544 1875539
190951 1046439
1006494 1596866
206518 527273
30700 804024
655225 14...

output:

137231299
983526275
308356937
668857536
945195729
943641074
175185008
617430910
464325003
693893932

result:

ok 10 lines

Test #16:

score: 5
Accepted
time: 63ms
memory: 32448kb

input:

10
192607 393179
201595 598364
94889 116297
68937 362063
375790 1173019
4169 213558
197175 1639344
8...

output:

675256418
743911917
169590876
438184575
303535039
821743664
735301178
652505454
446403563
727169327

result:

ok 10 lines

Test #17:

score: 5
Accepted
time: 191ms
memory: 32448kb

input:

10
798288 1987237
157453 1550357
705426 990370
613123 1321568
899033 956256
44168 172324
819515 1170...

output:

632430667
838490809
425855777
529713728
24505102
346102723
283846671
933284993
400547662
326488051

result:

ok 10 lines

Test #18:

score: 5
Accepted
time: 146ms
memory: 32448kb

input:

10
967864 1453914
481508 1761132
600063 853502
157152 1439130
76065 845828
663705 780511
192271 7895...

output:

127432855
408920662
120712126
633004380
672550015
788672447
919546999
290492241
915432205
505777533

result:

ok 10 lines

Test #19:

score: 5
Accepted
time: 100ms
memory: 32444kb

input:

10
933205 1384428
454383 955044
102873 1155697
143556 1235390
1498546 1673058
550403 1705906
44112 1...

output:

981751684
146672862
338003954
926693969
933443584
970830583
551138975
412430510
898397404
100973435

result:

ok 10 lines

Test #20:

score: 5
Accepted
time: 90ms
memory: 32444kb

input:

10
837543 861815
41145 74826
16836 20151
281906 835757
82984 232797
228888 347747
303856 369347
4196...

output:

425350707
303540825
51110377
610844679
381850715
397366972
193255813
384380765
774336313
888922281

result:

ok 10 lines