UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#204552#3614. 数序列smallstone100645ms71516kbC++11883b2024-06-02 10:06:492024-06-02 12:07:28

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//using LL = __int128
#define N 3111111
#define z 3000000
#define mod 1000000007ll
ll n, m, t, fac[N] = {1}, ifac[N], p[N] = {1};
ll qpow(ll x, ll y){
	ll ans = 1, tmp = x;
	while(y){
		if(y & 1)
			ans = (ans * tmp) % mod;
		tmp = (tmp * tmp) % mod;
		y >>= 1;
	}
	return ans;
}
ll calc(ll x, ll y){
	if(x < y)
		return 0;
	return fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
int main(){
	for(int i = 1 ; i <= z ; i++)
		fac[i] = fac[i - 1] * i % mod, p[i] = p[i - 1] * 2ll % mod;
	ifac[z] = qpow(fac[z], mod - 2);
	for(int i = z - 1 ; i >= 0 ; i--)
		ifac[i] = ifac[i + 1] * (i + 1) % mod;
	//cout << ifac[0];
	scanf("%lld", &t);
	for(int i = 1 ; i <= t ; i++){
		scanf("%lld%lld", &n, &m);
		printf("%lld\n", p[n - 3] * (n - 2) % mod * calc(m, n - 1) % mod);
	}
	return 0;
}

详细

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

Test #1:

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

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: 44ms
memory: 71512kb

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: 47ms
memory: 71516kb

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: 53ms
memory: 71512kb

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: 58ms
memory: 71516kb

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: 85ms
memory: 71512kb

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: 54ms
memory: 71516kb

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: 113ms
memory: 71516kb

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: 87ms
memory: 71512kb

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: 55ms
memory: 71512kb

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