QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#94114 | #6137. Sub-cycle Graph | CSU2023# | WA | 190ms | 7216kb | C++14 | 2.0kb | 2023-04-05 14:02:18 | 2023-04-05 14:02:22 |
Judging History
answer
#include <bits/stdc++.h>
template <class T>
inline void read(T &res)
{
char ch; bool flag = false; res = 0;
while (ch = getchar(), !isdigit(ch) && ch != '-');
ch == '-' ? flag = true : res = ch ^ 48;
while (ch = getchar(), isdigit(ch))
res = res * 10 + ch - 48;
flag ? res = -res : 0;
}
template <class T>
inline void put(T x)
{
if (x > 9)
put(x / 10);
putchar(x % 10 + 48);
}
template <class T>
inline void CkMin(T &x, T y) {x > y ? x = y : 0;}
const int N = 2e5 + 5;
const int lim = 2e5;
const int mod = 1e9 + 7;
int T_data, n, m;
int a[N], b[N], ex[N], iex[N], fac[N], ifac[N];
inline int quick_pow(int x, int k)
{
int res = 1;
while (k)
{
if (k & 1)
res = 1ll * res * x % mod;
x = 1ll * x * x % mod;
k >>= 1;
}
return res;
}
inline int C(int n, int m)
{
return 1ll * fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}
inline void add(int &x, int y)
{
x += y;
x >= mod ? x -= mod : 0;
}
inline void dec(int &x, int y)
{
x -= y;
x < 0 ? x += mod : 0;
}
int main()
{
fac[0] = ex[0] = 1;
for (int i = 1; i <= lim; ++i)
add(ex[i] = ex[i - 1], ex[i - 1]);
iex[lim] = quick_pow(ex[lim], mod - 2);
for (int i = lim; i >= 1; --i)
add(iex[i - 1] = iex[i], iex[i]);
for (int i = 1; i <= lim; ++i)
fac[i] = 1ll * i * fac[i - 1] % mod;
ifac[lim] = quick_pow(fac[lim], mod - 2);
for (int i = lim; i >= 1; --i)
ifac[i - 1] = 1ll * ifac[i] * i % mod;
read(T_data);
while (T_data--)
{
read(n); read(m);
if (m == n)
puts("1");
else if (m > n)
puts("0");
else
{
int k = n - m;
for (int i = 0; i <= k; ++i)
{
b[i] = 1ll * ex[k - i] * C(k, i) % mod;
if ((i & 1) && b[i])
b[i] = mod - b[i];
}
for (int i = k; i <= n; ++i)
a[i] = b[i - k];
int ans = 0;
for (int i = k; i <= n; ++i)
ans = (1ll * C(n - i + k - 1, k - 1) * a[i] + ans) % mod;
ans = 1ll * fac[n] * ifac[k] % mod * iex[k] % mod * ans % mod;
put(ans), putchar('\n');
for (int i = 0; i <= n; ++i)
a[i] = b[i] = 0;
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 6556kb
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: 190ms
memory: 7216kb
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 1 1 10 45 90 60 1 1 15 105 375 630 360 1 1 21 210 1155 3465 5040 2520 1 1 28 378 2940 13545 35280 45360 20160 1 1 36 630 6552 42525 170100 393120 453600 181440 1 1 45 990 13230 114345 643545 2286900 4762800 4989600 1814400 1 1 55 1485 24750 273735 2047815 10239075 32848200 62370000...
result:
wrong answer 9th numbers differ - expected: '3', found: '1'