QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#104941 | #2816. 过河卒二 | lonytree# | WA | 6ms | 6448kb | C++14 | 1.9kb | 2023-05-12 16:04:56 | 2023-05-12 16:04:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std; const int maxn = 2e5 + 5, mod = 1e9 + 7; typedef long long ll;
int ginv(int x) { return x == 1 ? 1 : (ll)(mod - mod / x) * ginv(mod % x) % mod; }
int inv[maxn];
int f[maxn], g[maxn];
inline int calc(int n, int m)
{
if (n < m) swap(n, m);
f[0] = n + m;
for (int i = 1; i < m << 1; i++) f[i] = (ll)f[i - 1] * (n + m - i) % mod;
// cerr << n << ' ' << m << ' ' << g[(m << 1) - 1] << endl;
g[(m << 1) - 1] = ginv(f[(m << 1) - 1]);
for (int i = (m << 1) - 2; i >= 0; i--) g[i] = (ll)g[i + 1] * (n + m - (i + 1)) % mod;
auto C = [&](int x, int y)->int
{
if (y == 0) return 1;
int L = (n + m) - (x - y + 1);
int R = (n + m) - (x + 1);
// cerr << n << ' ' << m << ' ' << x << ' ' << y << ' ' << L << ' ' << R << endl;
return (ll)f[L] * (R < 0 ? 1 : g[R]) % mod;
};
int res = 0;
for (int i = 0; i <= m; i++) res = (res + (ll)C(n + m - i * 2, m - i) * C(n + m - i, i) % mod * inv[i] % mod * inv[m - i]) % mod;
return res;
}
int N, M, K; pair<int, int> a[maxn];
int F[maxn];
int main()
{
for (int i = (inv[1] = 1) + 1; i < maxn; i++) inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
for (int i = inv[0] = 1; i < maxn; i++) inv[i] = (ll)inv[i - 1] * inv[i] % mod;
scanf("%d%d%d", &N, &M, &K);
for (int i = 1; i <= K; i++) scanf("%d%d", &a[i].first, &a[i].second), a[i].first--, a[i].second--;
sort(a + 1, a + K + 1);
int ans = calc(N, M);
for (int i = 1; i <= K; i++)
{
F[i] = calc(a[i].first, a[i].second);
for (int j = 1; j < i; j++) if (a[i].first >= a[j].first && a[i].second >= a[j].second)
F[i] = (F[i] - (ll)F[j] * calc(a[i].first - a[j].first, a[i].second - a[j].second)) % mod;
ans = (ans - (ll)F[i] * calc(N - a[i].first, M - a[i].second)) % mod;
}
return 0 * printf("%d\n", (ans + mod) % mod);
}
详细
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 6448kb
input:
1737 2613 20 1695 2081 1449 1419 868 1636 879 2454 1400 1778 1364 2166 1343 1563 1229 2012 1308 1674 1712 2004 1392 1716 1118 1690 1693 1986 1641 2221 1454 1937 1554 1944 997 2083 1242 1503 990 1834 986 1438
output:
833899701
result:
wrong answer 1st lines differ - expected: '47388', found: '833899701'