AT1983 [AGC001E] BBQ Hard 题解 - 题解 | Final Fantasy = xixike = 人间忽晚，山河已秋

# Description

Luogu 传送门

一直以为这是道数学题，结果是 $\text{dp}$ ……

观察题目给的式子，~~不难发现~~，这就是个长为 $a_i + a_j$ ，宽为 $b_i + b_j$ 的矩阵，让你求从左下角走到右上角的方案数。

转移方程也非常简单：

$dp_{i, j} = dp_{i - 1, j} + dp_{i, j - 1}$

但是转移完之后我们还是要 $O(n^2)$ 枚举统计答案，还是无法通过此题。

考虑如何优化统计答案的过程，使其变为 $O(n)$ 的。

我们需要消掉 $i$ 或 $j$ 中的一个，考虑平移。

我们把 $(0, 0)$ 到 $(a_i + a_j, b_i + b_j)$ 的矩形平移到 $(-a_i, -b_i)$ 到 $(a_j, b_j)$ ，不难证明这样的方案数是不会变的。

然后我们把处于第三象限的所有点都当作起点，也就是初值赋为 1，再跑一边上述 $\text{dp}$ ，然后 $O(n)$ 枚举统计答案即可。

需要注意的是题目中求的是一个上三角的和，所以要减去对角线的值再除以 2.

	#include <bits/stdc++.h>
	#define ll long long

	using namespace std;

	namespace IO{
	inline ll read(){
	ll x = 0;
	char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x;
	}

	template <typename T> inline void write(T x){
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 2e5 + 10;
	const int R = 2021;
	const int mod = 1e9 + 7;
	int n, ans;
	int a[N], b[N], fac[R << 2];
	int dp[R << 1][R << 1];

	inline int qpow(int a, int b){
	int res = 1;
	while(b){
	if(b & 1) res = 1ll * res * a % mod;
	a = 1ll * a * a % mod, b >>= 1;
	}
	return res;
	}

	inline int C(int n, int m){
	return 1ll * fac[n] * qpow(fac[m], mod - 2) % mod * qpow(fac[n - m], mod - 2) % mod;
	}

	signed main(){
	n = read();
	for(int i = 1; i <= n; ++i) a[i] = read(), b[i] = read();
	fac[0] = 1;
	for(int i = 1; i < (R << 2); ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
	for(int i = 1; i <= n; ++i) dp[R - a[i]][R - b[i]]++;
	for(int i = 1; i < (R << 1); ++i)
	for(int j = 1; j < (R << 1); ++j)
	dp[i][j] = (dp[i][j] + dp[i - 1][j] + dp[i][j - 1]) % mod;
	for(int i = 1; i <= n; ++i){
	ans = (ans + dp[R + a[i]][R + b[i]]) % mod;
	ans = (ans - C(2 * (a[i] + b[i]), 2 * a[i]) % mod + mod) % mod;
	}
	write(1ll * ans * qpow(2, mod - 2) % mod), puts("");
	return 0;
	}
	// X.K.