正睿二十连测
B
赛场上花了 \(40min\) 写了个暴力。赛后看题解 \(20min\) + 写 \(30min\)。
有多少个长度为 \(n\) 排列，使得 \(x(n - x + 1) \le m\) （\(x\) 为 \(n\) 的位置），答案对 \(p\) 取模。
令 \(f_n\) 表示长度为 \(n\) 的，满足条件的数量。枚举 \(n\) 的位置 \(i\)，两边互不干扰且答案只与相对大小有关。可以列出转移：
暴力转移可以拿到 \(56pts\)。
考虑优化！首先，若不考虑 \(x(n - x + 1) \le m\) 这个条件，\(f_n = n!\)。
因为 \(f_{i - 1}, f_{n - i}\) 对称，不妨设 \(i - 1 \le n - i\)。观察一下转移，若 \(i(n - i + 1) \le m\) 都成立了，实际上对于 \(n = i - 1\) 是显然满足 \(x(n - x + 1) \le m\) 的，即 \(f_{i - 1} = (i - 1)!\)。
那么转移就变成了 \(\sum\limits_{i = 1}^n (i - 1)!C_{n - 1}^{i - 1}f_{n - i}[i(n - i + 1) \le m] = (n - 1)!\sum\limits_{i = 1}^n [i(n - i + 1) \le m]\frac{f_{n - i}}{(n - i)!}\)。
注意到满足 \(i \le n - i + 1\) 且 \(i(n - i + 1) \le m\) 的 \(i\) 是一段前缀，直接利用前缀和进行转移即可。
时间复杂度：\(O(n)\)。
这个题难点在于转移的式子比较复杂，不好优化。发现 \(f_{i - 1}\) 一定是 \((i - 1)!\) 这个极其重要的性质后，转移简单了很多，使用前缀和优化即可。可惜没有找到这个性质。