公式解説と同様に, \(b\)の個数を数えて, それを\(N!\)倍することで答えを求めます.

\(c_n = b_n-n+1\)とします. \(c\)はソートされていて, 各項の差が偶数になる(つまり, 全ての項で偶奇が一致する)数列です. この\(c\)を数え上げます. \(b_1(=c_1)\)の偶奇で場合分けしてそれぞれ個数を数えます.

\(b_1\)が偶数のとき, 便宜的に\(c_0=0\), \(c_{N+1}=2\left\lfloor\frac {M-N}2\right\rfloor\)とし, \(d_n=\frac{c_n-c_{n-1}}2\)とすると, \(d\)は非負整数からなる数列で, \(d_1\)から\(d_{N+1}\)の和が\(\frac{c_{N+1}-c_0}2=\left\lfloor\frac {M-N}2\right\rfloor\)になります.

このような性質の数列は\(d\), \(c\)を通して\(b\)と対応付けられるので, これを数えればよく, 公式から

\[ \binom{\left\lfloor\frac {M-N}2\right\rfloor+N}N = \binom{\left\lfloor\frac {M+N}2\right\rfloor}N \]

と求められます.

\(b_1\)が奇数のときも同様にし, 便宜的に\(c_0=1\), \(c_{N+1}=2\left\lceil\frac {M-N}2\right\rceil-1\)とし, \(d_n=\frac{c_n-c_{n-1}}2\)とすると, \(d_1\)から\(d_{N+1}\)の和が\(\frac{c_{N+1}-c_0}2=\left\lceil\frac {M-N}2\right\rceil\)になり, 答えは

\[ \binom{\left\lceil\frac {M-N}2\right\rceil+N}N = \binom{\left\lceil\frac {M+N}2\right\rceil}N \]

になります.

この2つを足して\(N!\)倍すれば答えなので, つまり,

\[ N!\left(\binom{\left\lfloor\frac {M+N}2\right\rfloor}N+\binom{\left\lceil\frac {M+N}2\right\rceil}N\right) = \frac{\left\lfloor\frac {M+N}2\right\rfloor!}{\left\lfloor\frac {M-N}2\right\rfloor!}+\frac{\left\lceil\frac {M+N}2\right\rceil!}{\left\lceil\frac {M-N}2\right\rceil!} \]

が答えです. \(M<N\)のとき答えが\(0\)になることに気をつけてください.

解答例 (C++, 1ms)