{"problem":{"name":"「CGOI-3」残暴圣所","description":{"content":"为了通关残暴圣所，ac 需要在接下来的 $2n$ 个时刻进行 $n$ 次操作。第 $i$ 次操作需要在时刻 $l_i$ 按下某个按键，此后一直按住这个按键，直到时刻 $r_i$ 松开它（$l_i<r_i$）。在每个时刻，ac 要么按下一个按键，要么松开一个按键，但是可以同时按住多个按键。 第 $i$ 次操作形成了一个操作区间 $[l_i,r_i]$，满足 $l_i$ 严格递增。并且，由于残暴圣所","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8958"},"statements":[{"statement_type":"Markdown","content":"为了通关残暴圣所，ac 需要在接下来的 $2n$ 个时刻进行 $n$ 次操作。第 $i$ 次操作需要在时刻 $l_i$ 按下某个按键，此后一直按住这个按键，直到时刻 $r_i$ 松开它（$l_i<r_i$）。在每个时刻，ac 要么按下一个按键，要么松开一个按键，但是可以同时按住多个按键。\n\n第 $i$ 次操作形成了一个操作区间 $[l_i,r_i]$，满足 $l_i$ 严格递增。并且，由于残暴圣所的关卡设计，任意两个操作形成的操作区间之间，要么不交，要么包含。\n\nac 设计了 $2n$ 个难度系数 $a_1,a_2,\\dots,a_{2n}$。第 $i$ 次操作的难度可以用 $a_{l_i}\\times a_{r_i}$ 来评估，而通关残暴圣所的难度即为所有操作的难度之和。\n\n然而，由于 ac 卡在了残暴圣所的第一面，所以他并不知道每个操作的操作区间。在给定 $n$ 和 $\\{a\\}$ 的前提下，请你计算对于所有可能的情况，通关残暴圣所的难度之和，对 $998244353$ 取模。\n\n#### 形式化题意：\n\n给定一个长为 $2n$ 的数列 $a_1,a_2,\\dots,a_{2n}$。\n\n定义“区间组”由 $n$ 个区间组成，第 $i$ 个区间为 $[l_i,r_i]\\ (1\\le l_i<r_i\\le2n)$，求所有满足下列条件的区间组的 $\\sum_{i=1}^na_{l_i}\\times a_{r_i}$ 之和对 $998244353$ 取模：\n\n1. $l_1,r_1,l_2,r_2,\\dots,l_n,r_n$ 是 $1,2,\\dots,2n$ 的一个排列。\n2. $\\forall 1\\le i<n$，$l_i<l_{i+1}$。\n3. $\\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\n## Input\n\n第一行一个整数 $n$，表示区间数。\n\n第二行 $2n$ 个整数 $a_i$，含义如上所述。\n\n## Output\n\n一行一个整数，表示答案对 $998244353$ 取模的值。\n\n[samples]\n\n## Background\n\n终于打过春二心门的 ac 来到了春三，并决定预测一下残暴圣所（Ferocious Sanctuary）的难度。\n\n[![](https://cdn.luogu.com.cn/upload/image_hosting/xolrra48.png?x-oss-process=image/resize,m_lfit,h_340,w_450)](//www.bilibili.com/video/BV1Cg411v7Ji)\n\n## Note\n\n#### 样例说明\n\n对于样例 1，可能的两个操作区间只有两种情况：\n\n1. $[1,2],[3,4]$，通关难度为 $a_1a_2+a_3a_4=1612986$。\n2. $[1,4],[2,3]$，通关难度为 $a_1a_4+a_2a_3=1078706$。\n\n难度之和为 $1612986+1078706=2691692$，对 $998244353$ 取模后仍为 $2691692$。\n\n以下几种情况是不合法的：\n\n1. $[3,4],[1,2]$，因为要求 $l_i$ 严格递增，而 $l_1\\ge l_2$。\n2. $[1,1],[2,4]$，因为要求 $l_i<r_i$，而 $l_1\\ge r_1$。\n3. $[1,3],[2,3]$，因为要求在每个时刻，要么按下一个按键，要么松开一个按键，而第三个时刻松开了两个按键，第四个时刻没有按下或松开任何一个按键。\n4. $[1,3],[2,4]$，因为要求任意两个操作区间不交或包含，而这两个区间之间有交，并且没有包含关系。\n\n---\n\n#### 数据范围\n\n对于 $10\\%$ 的数据，$n\\le15$。\n\n对于 $30\\%$ 的数据，$n\\le200$。\n\n对于 $50\\%$ 的数据，$n\\le3000$。\n\n对于另 $5\\%$ 的数据，$a_i=1$。\n\n对于 $100\\%$ 的数据，$1\\le n\\le5\\times10^5$，$0\\le a_i<998244353$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8958","tags":["洛谷原创","O2优化","Catalan 数","快速傅里叶变换 FFT","快速数论变换 NTT"],"sample_group":[["2\n114 514 1919 810","2691692"],["3\n1 1 4 5 1 4","98"],["8\n275272885 418731188 289662326 114331587 192436268 885936831 877490593 508774565 633402863 149033362 995239139 494498006 168828873 138947653 983144753 844326228","349824160"]],"created_at":"2026-03-03 11:09:25"}}