嘘~ 正在从服务器偷取页面 . . .

[AGC001E] BBQ Hard 题解

发布日期: 2024-07-28

更新日期: 2024-07-29

文章字数: 706

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