包除原理を使います。\(\lbrace {1,2,\dots,N} \rbrace\) の部分集合 \(S\) 全てに対して以下の値を合計すればよいです。

• \(S\) に含まれるすべての要素 \(i\) に対して、\(|P_i - i| < X\) を満たす順列 \(P\) の個数 \(\times (-1)^{|S|}\)

これはつまり、\(P\) のいくつかの項を \(|P_i - i| < X\) を満たすように先に決め、決めた個数を \(k\) 個とすると残り \(N-k\) 項を適当に埋める方法 \((N-k)!\) と包除原理の係数 \((-1)^k\) を掛け合わせてそれを全ての方法について合計するということです。

動的計画法で答えを求めます。定義は以下です。

\(dp[i][j][k] = 1,2,\dots,i\) に対して \(P\) の項を先に決めるか考え、\(j\) 個を先に決めている。そして、先に \(P\) に入れた \(i-X\) 超過 \(i+X\) 未満の整数の集合は 2 進数で表すと \(k\) である。

\(dp[i][j][k]\) からの遷移は以下のように行います。

• \(P_{i+1}\) を先に決めないとき

\(dp[i+1][j][\left \lfloor \frac{k}{2} \right \rfloor]\) に \(dp[i][j][k]\) を加える。

• \(P_{i+1} = l\) と先に決めるとき(ただし、まだ \(l\) を \(P\) に使っておらず、\(i+1\) との差の絶対値が \(X\) 未満である必要がある。)

\(dp[i+1][j+1][\left \lfloor \frac{k}{2} \right \rfloor + 2^{l - (i+1) + X - 1}]\) に \(dp[i][j][k]\) を加える。

そして、\(0 \le j \le N,0 \le k < 2^{2X-1}\) を満たす整数の組 \((j,k)\) に対して \(dp[N][j][k] \times (N-j)! \times (-1)^j\) を足し合わせた値が答えです。

この動的計画法は、状態数 \(\mathrm{O}(N^2 4^X)\) 遷移 \(\mathrm{O}(X)\) であるため、この問題を \(\mathrm{O}(N^2 4^X X)\) で解くことが出来ます。