QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#93978 | #6137. Sub-cycle Graph | ksunhokim | AC ✓ | 1331ms | 4960kb | C++20 | 1.6kb | 2023-04-04 12:17:57 | 2023-04-04 12:18:01 |
Judging History
answer
#include <iostream>
using namespace std;
#define MOD 1000000007
#define MAXN 100005
long long fastExp(long long base, long long exp)
{
long long res = 1;
while (exp > 0)
{
if (exp & 1)
res = res * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return res;
}
long long modInverse(long long num)
{
return fastExp(num, MOD - 2);
}
long long fact[MAXN], inv[MAXN];
long long choose(int a, int b)
{
if (b == 0)
return 1;
return (fact[a] * inv[b] % MOD) * inv[a - b] % MOD;
}
long long solve()
{
long long n, m;
cin >> n >> m;
if (m > n)
return 0;
if (m == n)
return fact[n - 1] * modInverse(2) % MOD;
if (m == 0)
return 1;
long long ans = 0;
for (int i = 1; i <= min(m, n - m); i++)
{
long long cur = fact[n] * inv[n - m - i] % MOD;
//cout << "a" << cur << endl;
cur = cur * modInverse(fastExp(2, i)) % MOD;
cur = cur * inv[i] % MOD;
//cout << "b" << cur << endl;
cur = cur * choose(m - 1, i - 1) % MOD;
//cout << "c" << m - 1 << " " << i - 1 << endl;
ans += cur;
if (ans >= MOD)
ans -= MOD;
//cout << "cur: " << cur << endl;
}
return ans;
}
int main()
{
fact[0] = 1;
inv[0] = 1;
for (int i = 1; i < MAXN; i++)
{
fact[i] = i * fact[i - 1] % MOD;
inv[i] = modInverse(fact[i]);
}
int t;
cin >> t;
while (t--)
{
cout << solve() << endl;
}
}
详细
Test #1:
score: 100
Accepted
time: 13ms
memory: 4960kb
input:
3 4 2 4 3 5 3
output:
15 12 90
result:
ok 3 number(s): "15 12 90"
Test #2:
score: 0
Accepted
time: 1331ms
memory: 4888kb
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:
1 3 3 1 1 6 15 12 3 1 10 45 90 60 12 1 15 105 375 630 360 60 1 21 210 1155 3465 5040 2520 360 1 28 378 2940 13545 35280 45360 20160 2520 1 36 630 6552 42525 170100 393120 453600 181440 20160 1 45 990 13230 114345 643545 2286900 4762800 4989600 1814400 181440 1 55 1485 24750 273735 2047815 10239075 3...
result:
ok 17446 numbers