We use the inclusion-exclusion principle. It is sufficient to sum up the following value for all subsets \(S\) of \(\lbrace {1,2,\dots,N} \rbrace\):

• (the number of permutations \(P\) such that \(|P_i - i| < X\) for all elements \(i\) in \(S\)) \(\times (-1)^{|S|}\).

In other words, we find the sum of the products of “the number of ways to determine some of the terms of \(P\) to satisfy \(|P_i - i| < X\)”, “the number of ways \((N-k)!\) to fill the remaining \((N-k)\) terms”, and the coefficient of the inclusion-exclusion principle \((-1)^k\), where \(k\) is the number of per-determined terms.

We find the answer with a Dynamic Programming (DP) defined as follows:

\(dp[i][j][k] = \) Among \(1,2,\dots,i\), \(j\) terms are pre-determined. The set of integers between \(i-X\) and \(i+X\) (inclusive) that is used as pre-determined terms is represented by \(k\) as a binary.

The transitions from \(dp[i][j][k]\) as follows.

• If we do not pre-determine \(P_{i+1}\):

Add \(dp[i][j][k]\) to \(dp[i+1][j][\left \lfloor \frac{k}{2} \right \rfloor]\).

• If we pre-determine that \(P_{i+1} = l\) (as long as \(l\) is not used for \(l\) and the absolute difference between from \(i+1\) is \(X\) or less):

Add \(dp[i][j][k]\) to \(dp[i+1][j+1][\left \lfloor \frac{k}{2} \right \rfloor + 2^{l - (i+1) + X}]\).

The answer is the sum of \(dp[N][j][k] \times (N-j)! \times (-1)^j\) over all \((j,k)\) such that \(0 \le j \le N,0 \le k < 2^{2X+1}\).

Since this DP has \(\mathrm{O}(N^2 4^X)\) states and costs \(\mathrm{O}(X)\) for a transition, this problem can be solved in a total of \(\mathrm{O}(N^2 4^X X)\) time.