自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 22:44:05，当前版本为作者最后更新于2023-01-19 17:51:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题面中的神奇区间包含条件，本质上就是括号序列。所以先把题面换成人能听懂的语言：求出所有括号序列中每对括号的权值之和。

考虑枚举一对括号，计算这对括号会对多少种括号序列产生贡献。填入这一对括号后，括号内的部分可以乱填，去掉这对括号后括号外也可以乱填。设 $c_i$ 为卡特兰数的第 $i$ 项，那么括号 $[l,r]$ 产生贡献的括号序列种数为 $c_{\frac{r-l-1}2}\times c_{\frac{2n-r+l-1}2}$。枚举括号就可以通过 $50$ 分。

接下来把暴力的柿子列出来大力推导，其中约定 $b_{2n-i+1}=a_i$。

$$\begin{aligned} &\sum^{n}_{i=1}\sum^n_{j=i}(a_{2i-1}\times a_{2j}+a_{2i}\times a_{2j+1})\times c_{j-i}\times c_{n-j+i-1}\\ =&\sum^{n-1}_t\sum^{n-t}_{i=1}(a_{2i-1}\times a_{2(t+i)}+a_{2i}\times a_{2(t+i)+1})\times c_{t}\times c_{n-t-1}\\ =&\sum^{n-1}_tc_{t}\times c_{n-t-1}\sum^{n-t}_{i=1}(a_{2i-1}\times a_{2(t+i)}+a_{2i}\times a_{2(t+i)+1})\\ =&\sum^{n-1}_tc_{t}\times c_{n-t-1}\sum^{n-t}_{i=1}(a_{2i-1}\times b_{2n-2(t+i)+1}+a_{2i}\times b_{2n-2(t+i)})\\ =&\sum^{n-1}_tc_{t}\times c_{n-t-1}\sum^{n-t}_{i=1}(a_{2i-1}\times b_{2(n-t)-2i+1}+a_{2i}\times b_{2(n-t)-2i})\\ =&\sum^{n-1}_tc_{t}\times c_{n-t-1}\sum^{2(n-t)}_ia_i\times b_{2(n-t)-i}\\ \end{aligned} $$

设 $A(x)=\sum^{2n}_ia_ix^i$，$B(x)=\sum^{2n}_ib_ix^i$，$f(x)=A(x)B(x)$，则：

$$\begin{aligned} =&\sum^{n-1}_tc_{t}\times c_{n-t-1}\sum^{2(n-t)}_ia_i\times b_{2(n-t)-i}\\ =&\sum^{n-1}_tc_{t}\times c_{n-t-1}\times[x^{2(n-t)}]f(x)\\ \end{aligned} $$

一次卷积即可。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace polynomial {
//	by Register_int.
}

using namespace polynomial;

const int MAXN = 1e6 + 10;

int n, m; ll c[MAXN], ans;

poly<ll> f, g;

int main() {
	scanf("%d", &n), m = n << 1, c[0] = 1, f.resize(m + 1), g.resize(m + 1);
	for (int i = 1; i <= m; i++) scanf("%lld", &f[i]), g[m - i + 1] = f[i]; f *= g;
	for (int i = 1; i <= n; i++) c[i] = c[i - 1] * (4 * i - 2) % mod * inv(i + 1) % mod;
	for (int i = 0; i < n; i++) ans = (ans + c[i] * c[n - i - 1] % mod * f[n - i << 1] % mod) % mod;
	printf("%lld", ans);
}