[AT_abc313_d] Odd or Even
简单题，但是为什么赛场上 WA 了呢？
弱化题目，设 \(n = k + 1\)，发现只需要每一个数不取询问 \(k\) 次，通过前缀和得出。
再设 \(k + 1 \ | \ n\)，发现只需要类似分块即可解决。
回到原题，最后的一部分如何计算？我们可以对 \([n - k, n]\) 这个区间做询问，但是对于已经计算的数不再去除。把每一个得到的和减去前面已经计算的数的和就是真实的和，类似的也能计算出。
询问次数刚好为 \(n\)，时间复杂度为 \(\mathcal{O}(n)\)，可以通过此题。
P9493 「SFCOI-3」进行一个列的排
dp 好题。
首先手玩样例，考虑极端情况，发现 \(n-1\) 一定放左边或者右边。发现可以不考虑 \(n-1\)，则每个数只能放左边或者右边。
考虑只设一维的 \(dp_i\) 表示前 \(i\) 个数的合法情况，发现显然过不了样例，比如样例 \(1\)，我们发现 \(2\) 和 \(3\) 是不能放一起的。
那么容易列出 \(dp_{i,j}\) 表示前 \(i\) 个数中，\(j\) 个放左边的合法数量，转移方程易得。此题结。
核心代码：
g (i, n, 1) {
f (j, 0, n - i + 1) {
dp[i][j] = 0;
if (p[i] <= n - j && j > 0 && p[i] >= i - 1) dp[i][j] = dp[i + 1][j - 1];
if (p[i] <= j + i - 1 && n - i - j + 1 > 0 && p[i] >= i - 1) (dp[i][j] += dp[i + 1][j]) %= mod;
if (i == 2) (ans += dp[i][j]) %= mod;
}
}