ここでは、Writer 解法とは別の方法でアプローチしてみます。突然ですが、各要素が \(1\) 以上 \(N\) 以下の整数である（空でない）数列 \(c = (i_1,\dots,i_k)\) が

\[ A_{i_1} < A_{i_2} < \cdots < A_{i_k} \]

を満たすとき、\(c\) を鎖と呼ぶことにします。また、鎖 \(c\) について、\(s(c),t(c)\) をそれぞれ \(c\) の先頭の要素、末尾の要素とします。そうすると、\(1\) から \(N\) の順列 \(P\) について「\(A_{P_i} < A_{P_{i+1}}\) を満たすような \(1\leq i\leq N-1\) が \(K\) 個であること」と「\(P\) をできるだけ少ない個数の鎖に分割するときに \(N-K\) 個の鎖からなること」が同値となります。よって、各 \(1\leq i\leq N\) について、

\[ h(i) = |\{(c_1,\dots,c_i)\;|\;c_1,\dots,c_i\;は鎖,\; A_{t(c_k)} \geq A_{s(c_{k+1})}\;(1\leq k\leq i-1), \;各\;1,\dots,N\;は\;c_1,\dots,c_i\;のうちちょうど\;1 \;つにのみ現れる\}| \]

とすれば、求める答えは \(h(N-K)\) です。\(h(1),\dots,h(N)\) を直接求めるのは難しいので、条件を緩めて

\[ g(i) = |\{(c_1,\dots,c_i)\;|\;c_1,\dots,c_i\;は鎖, \;各\;1,\dots,N\;は\;c_1,\dots,c_i\;のうちちょうど\;1 \;つにのみ現れる\}| \]

を考えます。すると、\(g(1),\dots,g(N)\) は包除原理を用いて計算することができます。実際、

\[ f(i) = |\{(c_1,\dots,c_i)\;|\;c_1,\dots,c_i\;は鎖または空の数列, \;各\;1,\dots,N\;は\;c_1,\dots,c_i\;のうちちょうど\;1 \;つにのみ現れる\}| \]

とすると、

\[ g(i) = \sum_{j=1}^{i} \binom{i}{j}(-1)^{i-j} f(j) \]

が成立します。さらに、各 \(1\leq j\leq N\) について数列 \(A\) に \(j\) が現れる回数を \(b_j\) とすると

\[ f(i) = \prod_{j=1}^{N} i(i-1)\cdots(i-b_j+1) \]

であるため、まず \(f(1),\dots,f(N)\) を計算してから \(g(1),\dots, g(N)\) を計算できます。次に、この \(g(1),\dots,g(N)\) を用いて \(h(1),\dots,h(N)\) を求めることを考えます。ここでは除原理を用いることができます。すなわち、

\[ h(i) = g(i) - \sum_{j=1}^{i-1} \binom{N-j}{i-j}h(j) \]

が成立します。この式は、各 \(1,\dots,N\) が \(c_1,\dots,c_i\) のちょうど 1 つに現れるような鎖の列 \((c_1,\dots,c_i)\) で、\(A_{t(c_k)} < A_{s(c_{k+1})}\) となる \(1\leq k\leq i-1\) がちょうど \(i-j\) 個であるようなものの個数が \(\displaystyle\binom{N-j}{i-j}h(j)\) であることから従います（この部分が本解法の核となっているので、ぜひ証明を考えてみてください）。以上で、\(g(1),\dots,g(N)\) から \(h(1),\dots,h(N)\) を計算する方法がわかりました。二項係数の前計算を行っていれば、計算量は \(f(1),..,f(N)\)を求めるのに \(O(N^2)\)、\(g(1),..,g(N)\) を求めるのに \(O(N^2)\)、\(h(1),...,h(N)\) を求めるのに \(O(N^2)\) で、全体で \(O(N^2)\) となります。ここからはおまけですが、計算量を \(o(N^2)\) にすることができるので、その手法について簡単に説明します。

• \(b_j = k\) となる \(j\) の個数 \(c_k\) を前計算して、\(b_j\) が同じものについてまとめて累乗することで \(f(1),\dots,f(N)\) を計算量 \(O(N\sqrt{N})\) で求められる。
• 畳み込みを用いて \(g(1),\dots,g(N)\) を計算量 \(O(N \log N)\) で求められる。
• 分割統治 FFT を用いて \(h(1),\dots,h(N)\) を計算量 \(O(N\log ^2N)\) で求められる。

以上より、全体で計算量 \(O(N\sqrt{N})\) でこの問題を解くことができます。（追記：\(f(1),\dots,f(N)\) は多点評価を用いることで計算量 \(O(N\log^2 N)\) で求めることもできます。）

実装例 (c++)