[Solution] LNOI2022 problem

KaguyaH · 2022-05-26 20:23:42 · 题解

逆序对数为奇数的方案只有 \lbrace 1, 3, 2 \rbrace, \lbrace 2, 1, 3 \rbrace, \lbrace 3, 2, 1 \rbrace 三种。

设 f_{i, j, k, l, o, p, q} 表示前 i 个位置，目前凑出的 \lbrace 1 \rbrace, \lbrace 2 \rbrace, \lbrace 3 \rbrace, \lbrace 1, 3 \rbrace, \lbrace 2, 1 \rbrace, \lbrace 3, 2 \rbrace 的数目分别为 j, k, l, o, p, q 的方案数即可。第一维可以滚动数组。

时间复杂度 O(n^7)，常数极小，可过。由于 j + k + l + o + p + q \le n，所以事实上 (j, k, l, o, p, q) 的取值只有 \binom {25}{6} \approx 1.77 \times 10^5 种。