Problemagc001 E – BBQ Hard(组合数学)

agc001 E – BBQ Hard(组合数学)

题目链接:传送门

Description

\sum_{i=1}^{n}\sum_{j=1}^{i-1}\binom{A_i+B_i+A_j+B_j}{A_i+A_j}

Solution

我们通过观察式子可以发现题目就是要求所有(-A_i,-B_i)(A_j,B_j)的方案数(只能向上走或者向右走),于是我们可以用Dp来解决,初始化时在每个Dp[-A[i]] [-B[i]]处++,然后直接用Dp[i][j]+=Dp[i-1][j]+Dp[i][j-1]统计答案即可
然后因为我们求的j是< i的,所以需要减去一个(-A[i],-B[i])到自己的方案,并且最后的ans要除以2

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int Maxn = 200000, Maxm = 4000, Mod = (int)(1e9 + 7);

int A[Maxn + 10], B[Maxn + 10], Dp[Maxm * 2 + 10][Maxm * 2 + 10], fac[Maxn + 10], inv[Maxn + 10];
int N;

inline int Pow (LL a, int b)
{
    LL ans = 1;
    while (b)
    {
        if (b & 1) (ans *= a) %= Mod;
        (a *= a) %= Mod;
        b >>= 1;
    }
    return ans;
}

inline int C (int n, int m)
{
    return ((LL)fac[n] * inv[m] % Mod * inv[n - m] % Mod);
}

main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    scanf("%d", &N);
    fac[0] = 1;
    inv[0] = 1;
    for (int i = 1; i <= Maxn + 1; ++i) fac[i] = ((LL)fac[i - 1] * i) % Mod, inv[i] = Pow(fac[i], Mod - 2);
    for (int i = 1; i <= N; ++i)
    {
        scanf("%d%d", &A[i], &B[i]);
        Dp[2001 - A[i]][2001 - B[i]] ++;
        //cout<<Maxm + 1 - A[i]<<" "<<Maxm + 1 - B[i]<<endl;
    }
    for (int i = 1; i <= Maxm + 2; ++i)
        for (int j = 1; j <= Maxm + 2; ++j)
            (Dp[i][j] += Dp[i][j - 1] + Dp[i - 1][j]) %= Mod;
    LL ans = 0;
    for (int i = 1; i <= N; ++i)
    {
        ans += Dp[A[i] + 2001][B[i] + 2001];
        ans = ((ans - C(A[i] + A[i] + B[i] + B[i], A[i] + A[i])) % Mod + Mod) % Mod;
    }
    printf("%d\n", ans * inv[2] % Mod);
    return 0;
}

Categories: Problem Tags: , , ,

Comments

No Comments Yet. Be the first?

Post a comment