QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#94968 | #6137. Sub-cycle Graph | ysghwzp# | WA | 116ms | 4680kb | C++20 | 1.3kb | 2023-04-08 15:10:17 | 2023-04-08 15:10:19 |
Judging History
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'