题解

思路

对 $a<b<c<d$，有 $ad+bc<ac+bd<ab+cd$，因而得分达到全局最大值时，配对必须为 $(1,2),(3,4),\ldots,(2N-1,2N)$。

做法

对每一对元素，先决定谁在排列中更靠左，共有 $2^N$ 种；再决定 $N$ 个较左元素的相对顺序，共有 $N!$ 种。从左到右扫描排列时，已出现的较左元素数不能少于较右元素数，因此位置结构与长度 $2N$ 的合法括号序列一一对应，其数量是 Catalan 数 $\frac{1}{N+1}\binom{2N}{N}$。

总数为 $2^N N!\frac{1}{N+1}\binom{2N}{N}=2^N\frac{(2N)!}{(N+1)!}$，在模 $998244353$ 下直接计算 $2^N\prod_{i=N+2}^{2N}i$ 即可。

复杂度

时间复杂度为 $O(N)$，额外空间复杂度为 $O(1)$。