P8958 「CGOI-3」残暴圣所

题目背景

终于打过春二心门的 ac 来到了春三，并决定预测一下残暴圣所（Ferocious Sanctuary）的难度。

题目描述

为了通关残暴圣所，ac 需要在接下来的 $2 n$ 个时刻进行 $n$ 次操作。第 $i$ 次操作需要在时刻 $l_{i}$ 按下某个按键，此后一直按住这个按键，直到时刻 $r_{i}$ 松开它（ $l_{i} < r_{i}$ ）。在每个时刻，ac 要么按下一个按键，要么松开一个按键，但是可以同时按住多个按键。

第 $i$ 次操作形成了一个操作区间 $[l_{i}, r_{i}]$ ，满足 $l_{i}$ 严格递增。并且，由于残暴圣所的关卡设计，任意两个操作形成的操作区间之间，要么不交，要么包含。

ac 设计了 $2 n$ 个难度系数 $a_{1}, a_{2}, \dots, a_{2 n}$ 。第 $i$ 次操作的难度可以用 $a_{l_{i}} \times a_{r_{i}}$ 来评估，而通关残暴圣所的难度即为所有操作的难度之和。

然而，由于 ac 卡在了残暴圣所的第一面，所以他并不知道每个操作的操作区间。在给定 $n$ 和 ${a}$ 的前提下，请你计算对于所有可能的情况，通关残暴圣所的难度之和，对 $998244353$ 取模。

形式化题意

给定一个长为 $2 n$ 的数列 $a_{1}, a_{2}, \dots, a_{2 n}$ 。

定义“区间组”由 $n$ 个区间组成，第 $i$ 个区间为 $[l_{i}, r_{i}] (1 \leq l_{i} < r_{i} \leq 2 n)$ ，求所有满足下列条件的区间组的 $\sum_{i = 1}^{n} a_{l_{i}} \times a_{r_{i}}$ 之和对 $998244353$ 取模：

$l_{1}, r_{1}, l_{2}, r_{2}, \dots, l_{n}, r_{n}$ 是 $1, 2, \dots, 2 n$ 的一个排列。
$\forall 1 \leq i < n$ ， $l_{i} < l_{i + 1}$ 。
$\forall i, j$ ， $[l_{i}, r_{i}] \cap [l_{j}, r_{j}] = \emptyset$ 或 $[l_{i}, r_{i}] \sube [l_{j}, r_{j}]$ 或 $[l_{j}, r_{j}] \sube [l_{i}, r_{i}]$ 。

输入格式

第一行一个整数 $n$ ，表示区间数。

第二行 $2 n$ 个整数 $a_{i}$ ，含义如上所述。

输出格式

一行一个整数，表示答案对 $998244353$ 取模的值。

输入输出样例 #1

输入 #1

1 2	`2 114 514 1919 810`

输出 #1

输入输出样例 #2

输入 #2

1 2	`3 1 1 4 5 1 4`

输出 #2

输入输出样例 #3

输入 #3

1 2	`8 275272885 418731188 289662326 114331587 192436268 885936831 877490593 508774565 633402863 149033362 995239139 494498006 168828873 138947653 983144753 844326228`

输出 #3

1	`349824160`

说明/提示

样例说明

对于样例 1，可能的两个操作区间只有两种情况：

$[1, 2], [3, 4]$ ，通关难度为 $a_{1} a_{2} + a_{3} a_{4} = 1612986$ 。
$[1, 4], [2, 3]$ ，通关难度为 $a_{1} a_{4} + a_{2} a_{3} = 1078706$ 。

难度之和为 $1612986 + 1078706 = 2691692$ ，对 $998244353$ 取模后仍为 $2691692$ 。

以下几种情况是不合法的：

$[3, 4], [1, 2]$ ，因为要求 $l_{i}$ 严格递增，而 $l_{1} \geq l_{2}$ 。
$[1, 1], [2, 4]$ ，因为要求 $l_{i} < r_{i}$ ，而 $l_{1} \geq r_{1}$ 。
$[1, 3], [2, 3]$ ，因为要求在每个时刻，要么按下一个按键，要么松开一个按键，而第三个时刻松开了两个按键，第四个时刻没有按下或松开任何一个按键。
$[1, 3], [2, 4]$ ，因为要求任意两个操作区间不交或包含，而这两个区间之间有交，并且没有包含关系。

数据范围

对于 $10 %$ 的数据， $n \leq 15$ 。

对于 $30 %$ 的数据， $n \leq 200$ 。

对于 $50 %$ 的数据， $n \leq 3000$ 。

对于另 $5 %$ 的数据， $a_{i} = 1$ 。

对于 $100 %$ 的数据， $1 \leq n \leq 5 \times 10^{5}$ ， $0 \leq a_{i} < 998244353$ 。

题解

题面中对区间的各种限制，本质上就是合法括号序列。本题等价于求出所有括号序列中每对括号的权值之和。

对于括号 $[l, r]$ ，显然只有 $r - l + 1$ 为偶数的括号内才能出现合法的序列。考虑这对括号会在多少种括号序列中做贡献，方案数为括号内的方案数乘以序列删除区间 $[l, r]$ 后的方案数。

设 $c_{i}$ 为卡特兰数的第 $i$ 项，那么括号 $[l, r]$ 的贡献次数为 $c_{\frac{r - l - 1}{2}} \times c_{\frac{2 n - r + l - 1}{2}}$ 。

考虑到 $r - l + 1$ 必然为偶数，因此简单的方式是只枚举长度为偶数的括号 $[2 i - 1, 2 j]$ 或 $[2 i, 2 j + 1]$ 。我们可以得到以下式子，其中约定 $b_{2 n - i + 1} = a_{i}$ 。

\begin{aligned} \sum_{i = 1}^{n}\sum_{j = i}^{n}(a_{2 i - 1}\timesa_{2 j}+a_{2 i}\timesa_{2 j + 1})\timesc_{j - i}\timesc_{n - j + i - 1} \\ = & \sum_{t = 1}^{n - 1}\sum_{i = 1}^{n - t}(a_{2 i - 1}\timesa_{2 (t + i)}+a_{2 i}\timesa_{2 (t + i) + 1})\timesc_{t}\timesc_{n - t - 1} \\ = & \sum_{t = 1}^{n - 1}c_{t}\timesc_{n - t - 1}\sum_{i = 1}^{n - t}(a_{2 i - 1}\timesa_{2 (t + i)}+a_{2 i}\timesa_{2 (t + i) + 1}) \\ = & \sum_{t = 1}^{n - 1}c_{t}\timesc_{n - t - 1}\sum_{i = 1}^{n - t}(a_{2 i - 1}\timesb_{2 n - 2 (t + i) + 1}+a_{2 i}\timesb_{2 n - 2 (t + i)}) \\ = & \sum_{t = 1}^{n - 1}c_{t}\timesc_{n - t - 1}\sum_{i = 1}^{n - t}(a_{2 i - 1}\timesb_{2 (n - t) - 2 i + 1}+a_{2 i}\timesb_{2 (n - t) - 2 i}) \\ = & \sum_{t = 1}^{n - 1}c_{t}\timesc_{n - t - 1}\sum_{i = 1}^{2 (n - t)}a_{i}\timesb_{2 (n - t) - i} \end{aligned}

构造多项式

A (x) = \sum_{i}^{2 n} a_{i} x^{i}

则原式可转化为：

\begin{aligned} 原式 = & \sum_{t = 1}^{n - 1}c_{t}\timesc_{n - t - 1}\sum_{i}^{2 (n - t)}a_{i}\timesb_{2 (n - t) - i} \\ = & \sum_{t = 1}^{n - 1}c_{t}\timesc_{n - t - 1}\times[x^{2 (n - t)}]f(x) \end{aligned}

一次卷积即可。