UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#204547#3614. 数序列drdilyor100879ms48068kbC++919b2024-06-02 09:18:202024-06-02 12:06:53

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int fac[3000005],ifac[3000005];
int qkp(int b,int p){
    int r=1;
    while(p){
        if(p&1)(r*=b)%=mod;
        p/=2;
        (b*=b)%=mod;
    }
    return r;
}
int C(int n,int m){
    if(n<m)return 0;
    return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
void solve(){
    int n,m;
    cin>>n>>m;
    cout<<C(m,n-1)*(n-2)%mod*qkp(2,n-3)%mod<<"\n";
    //先给一个上升的.
    //1 1 2
    //1 1 3
    //2 2 3
    //1 2 2 3 4.
    //C(m,n-1)*(n-2)*
    //i=0~n-3
    //2^(n-3)
    //C(n-3,i-2)
    //1<=x1<x2<...<xn<=m.
}
signed main(){
    fac[0]=1;
    for(int i=1;i<=3000000;i++)fac[i]=fac[i-1]*i%mod;
    ifac[3000000]=qkp(fac[3000000],mod-2);
    for(int i=2999999;i>=0;i--){
        ifac[i]=ifac[i+1]*(i+1)%mod;
    }
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

详细

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

Test #1:

score: 10
Accepted
time: 47ms
memory: 48068kb

input:

7
3 3
3 7
5 6
4 6
6 7
4 7
7 7

output:

3
21
180
80
672
140
560

result:

ok 7 lines

Test #2:

score: 10
Accepted
time: 49ms
memory: 48064kb

input:

7
3 7
4 7
5 7
4 4
6 7
6 6
7 7

output:

21
140
420
16
672
192
560

result:

ok 7 lines

Test #3:

score: 10
Accepted
time: 35ms
memory: 48068kb

input:

300
9 86
134 136
97 240
69 250
53 194
129 134
178 199
25 204
230 242
151 287
139 164
296 296
107 251...

output:

40526723
469730673
304633950
923531840
718764556
110519525
835573061
832250518
680058466
735230005
2...

result:

ok 300 lines

Test #4:

score: 10
Accepted
time: 47ms
memory: 48068kb

input:

300
173 232
33 222
8 176
46 63
13 202
178 229
108 111
15 64
113 184
94 154
88 234
144 206
9 49
79 24...

output:

224604879
277347795
811551007
567680834
960046456
517237847
348212471
569492317
11434468
777076555
5...

result:

ok 300 lines

Test #5:

score: 10
Accepted
time: 34ms
memory: 48068kb

input:

5000
412 1366
1482 2126
2935 3390
348 1645
2970 3305
1215 4683
1038 4391
1270 3893
1302 2624
2992 45...

output:

523565415
539691845
654556161
657048522
326493326
91224752
620062159
795068501
536003594
759861732
8...

result:

ok 5000 lines

Test #6:

score: 10
Accepted
time: 27ms
memory: 48068kb

input:

5000
1934 3816
2611 3542
3523 3924
2144 2499
3909 4913
1387 2297
4038 4078
453 4941
2348 4244
775 17...

output:

151839675
731371158
489658176
826901708
431639651
603140569
878658019
509019045
786086713
113182975
...

result:

ok 5000 lines

Test #7:

score: 10
Accepted
time: 39ms
memory: 48068kb

input:

5000
1269 1442
604 3097
2445 4112
1666 4657
1857 4513
2895 3574
1752 4054
3005 4635
865 3393
1542 39...

output:

524692351
827841308
513781360
479373012
366445825
853293680
198475288
880692057
19768510
139303486
2...

result:

ok 5000 lines

Test #8:

score: 10
Accepted
time: 158ms
memory: 48068kb

input:

100000
1587 61724
74142 75295
5013 90103
5917 35473
25075 85737
13710 84637
22733 78012
53405 54177
...

output:

845899029
489414747
121612187
397260957
9071444
793562505
471919816
402782778
182689858
209987455
42...

result:

ok 100000 lines

Test #9:

score: 10
Accepted
time: 238ms
memory: 48068kb

input:

100000
7882 93963
28821 74195
67970 76130
72396 94880
48577 59222
43195 52210
8611 26920
41643 99429...

output:

49480540
267228382
984545612
357166580
378960858
569567369
308299687
618651512
33189840
518149630
47...

result:

ok 100000 lines

Test #10:

score: 10
Accepted
time: 205ms
memory: 48068kb

input:

100000
80636 86342
56899 99692
45837 73847
12279 54289
11417 93368
75154 90711
21086 49229
18857 291...

output:

386685220
486470069
213711686
833366511
70175852
873949632
848304112
691923059
359042554
547872718
7...

result:

ok 100000 lines

Extra Test:

score: 0
Extra Test Passed