P8958 题解

· · 题解

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

考虑枚举一对括号，计算这对括号会对多少种括号序列产生贡献。填入这一对括号后，括号内的部分可以乱填，去掉这对括号后括号外也可以乱填。设 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);
}