この問題の答えは、以下の問題の答えと同じです。

\((1, 2, \dots , N)\) の順列 \(P = (P_{1}, P_{2}, \dots P_{N})\) であって、以下の条件を満たすものを良い順列とします。

• 谷型になっている。つまり、\(1\) 以上 \(N\) 以下の整数 \(k\) であって、以下の条件を全て満たすものが存在する。
  • \(1\) 以上 \(k\) 未満の任意の整数 \(i\) に対して、 \(P_{i} > P_{i + 1}\) を満たす。
  • \(k\) 以上 \(N\) 未満の任意の整数 \(i\) に対して、 \(P_{i} < P_{i + 1}\) を満たす。

良い順列 の組 \((A, B)\) であって、\(\max(A_{a}, B_{b}) = k\) を満たすものは何通りありますか。

以下の問題の答えを \(f(s, t)\) とします。

良い順列 \(P\) であって、 \(P_{s} = t\) であるものは何通りありますか。

\(f(s, t)\) について、以下が成り立ちます。

• \(t = 1\) のとき、 \(f(s, t) = \dbinom{N - 1}{s - 1}\)
• \(t \neq 1\) のとき、 \(f(s, t) = 2^{t - 2}\left(\dbinom{N - t}{s - 1} + \dbinom{N - t}{N - s}\right)\)

本問題の答えは \(f\) を用いて、以下のように表されます。

\[\left(\sum_{i = 1}^{k} f(a, i)\right)\cdot\left(\sum_{i = 1}^{k}f(b,i)\right) - \left(\sum_{i = 1}^{k - 1} f(a, i)\right)\cdot\left(\sum_{i = 1}^{k - 1}f(b,i)\right)\]

\(f\) について累積和を先に求めることで、この問題の答えを \(O(N + Q)\) で求めることができます。

実装例 pypy 733ms