QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104941#2816. 过河卒二lonytree#WA 6ms6448kbC++141.9kb2023-05-12 16:04:562023-05-12 16:04:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-12 16:04:58]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:6448kb
  • [2023-05-12 16:04:56]
  • 提交

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);
}

Details

Tip: Click on the bar to expand more detailed information

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'