题目背景
终于打过春二心门的 ac 来到了春三，并决定预测一下残暴圣所（Ferocious Sanctuary）的难度。
题目描述
为了通关残暴圣所，ac 需要在接下来的 $2n$ 个时刻进行 $n$ 次操作。第 $i$ 次操作需要在时刻 $l_i$ 按下某个按键，此后一直按住这个按键，直到时刻 $r_i$ 松开它（$l_i<r_i$）。在每个时刻，ac 要么按下一个按键，要么松开一个按键，但是可以同时按住多个按键。
第 $i$ 次操作形成了一个操作区间 $[l_i,r_i]$，满足 $l_i$ 严格递增。并且，由于残暴圣所的关卡设计，任意两个操作形成的操作区间之间，要么不交，要么包含。
ac 设计了 $2n$ 个难度系数 $a_1,a_2,\dots,a_{2n}$。第 $i$ 次操作的难度可以用 $a_{l_i}\times a_{r_i}$ 来评估，而通关残暴圣所的难度即为所有操作的难度之和。
然而，由于 ac 卡在了残暴圣所的第一面，所以他并不知道每个操作的操作区间。在给定 $n$ 和 ${a}$ 的前提下，请你计算对于所有可能的情况，通关残暴圣所的难度之和，对 $998244353$ 取模。
形式化题意
给定一个长为 $2n$ 的数列 $a_1,a_2,\dots,a_{2n}$。
定义“区间组”由 $n$ 个区间组成，第 $i$ 个区间为 $[l_i,r_i]\ (1\le l_i<r_i\le2n)$，求所有满足下列条件的区间组的 $\sum_{i=1}^na_{l_i}\times a_{r_i}$ 之和对 $998244353$ 取模：
- $l_1,r_1,l_2,r_2,\dots,l_n,r_n$ 是 $1,2,\dots,2n$ 的一个排列。
- $\forall 1\le i<n$，$l_i<l_{i+1}$。
- $\forall i,j$，$[l_i,r_i]\cap[l_j,r_j]=\varnothing$ 或 $[l_i,r_i]\sube[l_j,r_j]$ 或 $[l_j,r_j]\sube[l_i,r_i]$。
输入格式
第一行一个整数 $n$，表示区间数。
第二行 $2n$ 个整数 $a_i$，含义如上所述。
输出格式
一行一个整数，表示答案对 $998244353$ 取模的值。
输入输出样例 #1
输入 #1
1 | |
输出 #1
1 | |
输入输出样例 #2
输入 #2
1 | |
输出 #2
1 | |
输入输出样例 #3
输入 #3
1 | |
输出 #3
1 | |
说明/提示
样例说明
对于样例 1，可能的两个操作区间只有两种情况：
- $[1,2],[3,4]$，通关难度为 $a_1a_2+a_3a_4=1612986$。
- $[1,4],[2,3]$，通关难度为 $a_1a_4+a_2a_3=1078706$。
难度之和为 $1612986+1078706=2691692$，对 $998244353$ 取模后仍为 $2691692$。
以下几种情况是不合法的：
- $[3,4],[1,2]$，因为要求 $l_i$ 严格递增，而 $l_1\ge l_2$。
- $[1,1],[2,4]$，因为要求 $l_i<r_i$，而 $l_1\ge r_1$。
- $[1,3],[2,3]$，因为要求在每个时刻，要么按下一个按键，要么松开一个按键，而第三个时刻松开了两个按键，第四个时刻没有按下或松开任何一个按键。
- $[1,3],[2,4]$，因为要求任意两个操作区间不交或包含，而这两个区间之间有交，并且没有包含关系。
数据范围
对于 $10%$ 的数据，$n\le15$。
对于 $30%$ 的数据，$n\le200$。
对于 $50%$ 的数据，$n\le3000$。
对于另 $5%$ 的数据，$a_i=1$。
对于 $100%$ 的数据，$1\le n\le5\times10^5$，$0\le a_i<998244353$。
题解
题面中对区间的各种限制，本质上就是合法括号序列。本题等价于求出所有括号序列中每对括号的权值之和。
对于括号 $[l,r]$，显然只有 $r-l+1$ 为偶数的括号内才能出现合法的序列。考虑这对括号会在多少种括号序列中做贡献，方案数为括号内的方案数乘以序列删除区间 $[l,r]$ 后的方案数。
设 $c_i$ 为卡特兰数的第 $i$ 项，那么括号 $[l, r]$ 的贡献次数为 $c_{\frac{r-l-1}{2}} \times c_{\frac{2n-r+l-1}{2}}$。
考虑到 $r-l+1$ 必然为偶数，因此简单的方式是只枚举长度为偶数的括号 $[2i-1,2j]$ 或 $[2i,2j+1]$。我们可以得到以下式子，其中约定 $b_{2n-i+1} = a_i$。
$$ \begin{align*} & \sum_{i=1}^{n} \sum_{j=i}^{n} (a_{2i-1} \times a_{2j} + a_{2i} \times a_{2j+1}) \times c_{j-i} \times c_{n-j+i-1} \ = & \sum_{t=1}^{n-1} \sum_{i=1}^{n-t} (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_{t=1}^{n-1} c_t \times c_{n-t-1} \sum_{i=1}^{n-t} (a_{2i-1} \times a_{2(t+i)} + a_{2i} \times a_{2(t+i)+1}) \ = & \sum_{t=1}^{n-1} c_t \times c_{n-t-1} \sum_{i=1}^{n-t} (a_{2i-1} \times b_{2n-2(t+i)+1} + a_{2i} \times b_{2n-2(t+i)}) \ = & \sum_{t=1}^{n-1} c_t \times c_{n-t-1} \sum_{i=1}^{n-t} (a_{2i-1} \times b_{2(n-t)-2i+1} + a_{2i} \times b_{2(n-t)-2i}) \ = & \sum_{t=1}^{n-1} c_t \times c_{n-t-1} \sum_{i=1}^{2(n-t)} a_i \times b_{2(n-t)-i} \ \end{align*} $$
构造多项式
$$ A(x) = \sum_{i}^{2n} a_i x^i \ B(x) = \sum_{i}^{2n} b_i x^i \ f(x) = A(x)B(x) $$
则原式可转化为：
$$ \begin{align*} \text{原式} = & \sum_{t=1}^{n-1} c_t \times c_{n-t-1} \sum_{i}^{2(n-t)} a_i \times b_{2(n-t)-i} \ = & \sum_{t=1}^{n-1} c_t \times c_{n-t-1} \times [x^{2(n-t)}]f(x) \ \end{align*} $$
一次卷积即可。
