[AGC001E] BBQ Hard 题解

题目链接：[AGC001E] BBQ Hard

题意：

有 \(n\) 个数对 \((a_i, b_i)\)，求出 \[ \sum_{i=1}^{n}\sum_{j=i + 1}^{n}{a_i+b_i+a_j+b_j \choose a_i+a_j} \] 答案对 \(10 ^ 9 + 7\) 取模。

数据范围：

\(1 \le n \le 2\times 10^5,~1 \le a_i,b_i \le 2000\) 。

这道题有利用组合意义的解法，这里来讲讲 OGF 的解法吧。

先考虑较为简单的 \[ \sum_{i=1}^n \sum_{j=1}^n\binom{a_i+b_i+a_j+b_j}{a_i+a_j} \] 推式子，启动！ \[ \begin{aligned} & \sum_{i=1}^n \sum_{j=1}^n\binom{a_i+b_i+a_j+b_j}{a_i+a_j} \\[6pt]& =\left[x^{a_i+a_j}\right] \sum_{i=1}^n \sum_{j=1}^n(1+x)^{t_i+t_j} && t_i=a_i+b_i \\[6pt]& =\left[x^0\right] \sum_{i=1}^n \sum_{j=1}^n x^{-a_i-a_j}(1+x)^{t_i+t_j} \\[6pt]& =\left[x^0\right]\left(\sum_{i=1}^n x^{-a_i}(1+x)^{t_i}\right)^2 \\[6pt]& =\left[x^0\right]\left(\sum_{i=1}^m Q_i(1+x)^i\right)^2 && Q_k=\sum_{t_i=k} x^{-a_i} \end{aligned} \] 显然 \(t_i=k\) 的 \(i\) 可以开一个 vector 求出来

而 \(\sum_{i=1}^m Q_i(1+x)^i\) 是一个很容易计算的卷积，这里相当于把每个 \(x^{-a_i}\) 的系数加上了 \(1\)

外层的平方由于我们只需要第 \(0\) 项，因此也很容易得到，那么式子就求出来了。

然后回到原题，显然只需要减去相等的情况再除以二就好了，于是这题就做完了。

时间复杂度 \(\mathcal{O}(n + m^2)\) ，这里 \(m\) 是值域。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define M ((int)(8e3 + 55))
#define N ((int)(2e5 + 15))
const int c = 4e3 + 15;

vector<int> vec[M];
int res, a[N], b[N], fac[M], infac[M], ans[M];
int qpow(int a, int b)
{
    int r = 1;
    for(a %= mod; b; b >>= 1, a = a * a % mod)
        if(b & 1) r = r * a % mod;
    return r;
}
int C(int n, int m)
{
    if(n < m || m < 0) return 0;
    return fac[n] * infac[m] % mod * infac[n - m] % mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    fac[0] = 1;
    rep(i, 1, M - 5) fac[i] = fac[i - 1] * i % mod;
    infac[M - 5] = qpow(fac[M - 5], mod - 2);
    Rep(i, M - 5 - 1, 0) infac[i] = infac[i + 1] * (i + 1) % mod;
    int n; cin >> n;
    rep(i, 1, n)
    {
        cin >> a[i] >> b[i];
        vec[a[i] + b[i]].push_back(-a[i] + c);
    }
    Rep(i, c, 1)
    {
        for(int x : vec[i]) add(ans[x], 1);
        Rep(j, M - 5, 1) add(ans[j], ans[j - 1]);
    }
    rep(i, -c, c) add(res, ans[c - i] * ans[c + i] % mod);
    rep(i, 1, n) add(res, (mod - C(2 * a[i] + 2 * b[i], 2 * a[i]) % mod) % mod);
    cout << res * qpow(2, mod - 2) % mod << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/3gow80xv