QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94968#6137. Sub-cycle Graphysghwzp#WA 116ms4680kbC++201.3kb2023-04-08 15:10:172023-04-08 15:10:19

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-08 15:10:19]
  • 评测
  • 测评结果:WA
  • 用时:116ms
  • 内存:4680kb
  • [2023-04-08 15:10:17]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1E5;
constexpr int P = 1E9 + 7;

int fac[N + 1], invfac[N + 1], inv[N + 1];

int power(int a, int b) {
	int res = 1;
	for (; b; b /= 2, a = 1LL * a * a % P) {
		if (b % 2) {
			res = 1LL * res * a % P;
		}
	}
	return res;
}

int binom(int n, int m) {
	if (n < m || m < 0) {
		return 0;
	}
	return 1LL * fac[n] * invfac[m] % P * invfac[n - m] % P;
}

void solve() {
	int n;
	i64 m;
	std::cin >> n >> m;

	if (n < m) {
		std::cout << 0 << "\n";
		return;
	}

	if (n == m) {
		std::cout << 1LL * fac[n - 1] * (P + 1) / 2 % P << "\n";
		return;
	}

	m = n - m;
	int ans = 0;
	for (int i = 0; i < m; i++) {
		ans = (ans + 1LL * binom(m, i) * binom(n - m + m - i - 1, m - i - 1)) % P;
	}
	ans = 1LL * ans * fac[n] % P * invfac[m] % P * power((P + 1) / 2, m) % P;
	std::cout << ans << "\n";
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	fac[0] = 1;
	for (int i = 1; i <= N; i++) {
		fac[i] = 1LL * fac[i - 1] * i % P;
	}
	invfac[N] = power(fac[N], P - 2);
	for (int i = N; i; i--) {
		invfac[i - 1] = 1LL * invfac[i] * i % P;
		inv[i] = 1LL * invfac[i] * fac[i - 1] % P;
	}

	int T;
	std::cin >> T;

	while (T--) {
		solve();
	}

	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4680kb

input:

3
4 2
4 3
5 3

output:

15
12
90

result:

ok 3 number(s): "15 12 90"

Test #2:

score: -100
Wrong Answer
time: 116ms
memory: 4492kb

input:

17446
3 0
3 1
3 2
3 3
4 0
4 1
4 2
4 3
4 4
5 0
5 1
5 2
5 3
5 4
5 5
6 0
6 1
6 2
6 3
6 4
6 5
6 6
7 0
7 1
7 2
7 3
7 4
7 5
7 6
7 7
8 0
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
9 0
9 1
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
10 0
10 1
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
11 0
11 1
11 2
11 3
11 4
11 5
11 6
11 7
11...

output:

875000007
3
3
1
437500004
6
15
12
3
718750006
10
45
90
60
12
859375007
15
105
375
630
360
60
429687504
21
210
1155
3465
5040
2520
360
714843756
28
378
2940
13545
35280
45360
20160
2520
857421882
36
630
6552
42525
170100
393120
453600
181440
20160
928710945
45
990
13230
114345
643545
2286900
4762800
...

result:

wrong answer 1st numbers differ - expected: '1', found: '875000007'