AGC - 洛谷保存站

### [[AGC001D] Arrays and Palindrome](https://www.luogu.com.cn/problem/AT_agc001_d)

### [[AGC001E] BBQ Hard](https://www.luogu.com.cn/problem/AT_agc001_e)

$\color{#9d3dcf}10.2$

化一下问题，现在要求：
$$
\sum_{i=1}^n\sum_{j=1}^n\binom{a_i+b_i+a_j+b_j}{a_i+a_j}
$$
直接 GF：
$$
\begin{aligned}
\fbox{原式}&=\sum_{i=1}^n\sum_{j=1}^n[x^{a_i+a_j}](1+x)^{a_i+b_i+a_j+b_j}\\
&=\sum_{i=1}^n\sum_{j=1}^n[x^0]x^{-a_i-a_j}(1+x)^{a_i+b_i+a_j+b_j}\\
&=[x^0]\left(\sum_{i=1}^nx^{-a_i}(1+x)^{a_i+b_i}\right)^2
\end{aligned}
$$
考虑怎么求括号里那一坨玩意，直接 $\mathcal O(nm)$ 做是不可行的，考虑转为枚举 $a_i+b_i$：
$$
\begin{aligned}
\fbox{原式}&=\sum_{i=1}^{m}(1+x)^i\sum_{j=1}^n[a_j+b_j=i]x^{-a_j}
\end{aligned}
$$
设后面那一坨为 $G_i(x)$，暴力乘是 $\mathcal O(m^3)$ 或者 $\mathcal O(m^2\log m)$ 的，不过看到形如 $\sum\limits_{i=0}^nF^i(x)G_i(x)$ 的形式并且 $F$ 次数很低，可以使用秦九韶算法，也即化为 $(\dots((G_n(x)F(x)+G_{n-1}(x))F(x)+G_{n-2}(x))F(x)+\dots+G_1(x))F(x)+G_0(x)$，复杂度优化至 $\mathcal O(n+m^2)$。

```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, M = 8e3 + 5, D = 4e3, p = 1e9 + 7;
int n, a[N], b[N], f[M], fac[M], inv[M], ans;
basic_string<int> G[M];
int qpow(int a, int b) { int c = 1; while (b) { if (b & 1) c = (ll)c * a % p; a = (ll)a * a % p, b >>= 1; } return c; }
int C(int n, int m) { return n < m ? 0 : (ll)fac[n] * inv[n - m] % p * inv[m] % p; }
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0), cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i] >> b[i], G[a[i] + b[i]] += D - a[i];
	for (int i = D; i; i--) {
		for (int j : G[i]) f[j]++;
		for (int j = M - 1; j; j--) f[j] += f[j - 1], f[j] -= p & -(f[j] >= p);
	}
	for (int i = -D; i <= D; i++) ans = (ans + (ll)f[D - i] * f[D + i]) % p;
	fac[0] = 1; for (int i = 1; i < M; i++) fac[i] = (ll)fac[i - 1] * i % p;
	inv[M - 1] = qpow(fac[M - 1], p - 2); for (int i = M - 2; ~i; i--) inv[i] = (ll)inv[i + 1] * (i + 1) % p;
	for (int i = 1; i <= n; i++) ans = (ans - C(a[i] + b[i] << 1, a[i] << 1) + p) % p;
	cout << (ll)ans * (p + 1 >> 1) % p;
}
```

### [[AGC001F] Wide Swap](https://www.luogu.com.cn/problem/AT_agc001_f)

正在渲染内容...