发现不太好直接求，考虑将 \(P\) 映射到 \(P^{-1}\) 上，这样题目中的条件就变成了 \(|P_i-P_{i+M}|=1\)。因此我们可以对模 \(M\) 的每个剩余系做 \(M=1\) 的情况，然后最后快速幂合并。
考虑 \(M=1\) 的情况怎么做。记 \(f_i\) 表示 \(K=i\) 的方案数，考虑容斥，再记 \(g_k\) 表示钦定 \(k\) 个间隔满足两边的数差为 \(1\) 的方案数，二项式反演可得：
\[f_{i}=\sum_{j=i}^n{j\choose i}\cdot(-1)^{j-i}\cdot g_{j} \]这个东西是可以 NTT 算的，具体的方法是将 \(f,g\) 分别反转变成可以多项式乘法的形式：
\[f_{i}=\sum_{j=0}^{i}{n-j\choose n-i}\cdot(-1)^{i-j}\cdot g_{j} \]考虑怎么求 \(g_k\)。我们对于每个选出的间隔将其两边的数合并，这样每个剩余系就被分成了若干段，每段中的数连续，总共有 \(N-k\) 段。关于值的分配，方案数显然为 \((N-k)!\cdot 2^\text{段长大于一的段的个数}\) 最后给 \(g_k\) 乘上即可。
考虑一个大小为 \(n\) 的剩余系划分方案怎么求。记 \(g'_k\) 表示钦定 \(k\) 个间隔的方案数，我们可以写出 \(g'\) 的生成函数：\(g'_k=[x^n]F(x)^{n-k}\)，其中 \(F(x)=x+2x^2+2x^3+\dots\)。发现 \(F(x)=\frac{2x}{1-x}-x\)，这时候可以想到一个经典的式子：
\[\left(\frac{1}{1-x}\right)^k=\sum_{n=0}^{\infty}{n+k-1\choose n}x^n \]（通过对 \(\frac{1}{1-x}=\sum_{i\ge0} x^i\) 两边求 \(k-1\) 次导数得到）
故：
\[[x^n]F(x)^{n-k}=\sum_{i=0}^{n-k}{n-k\choose i}\cdot{n-i-1\choose k}\cdot(-1)^i\cdot2^{n-k-i} \]这个东西可以 NTT 算。最后由于 \(n\) 只有两种可能值，分别求出 \(g'\) 再做个快速幂合并即可。
然后就做完了。
标签：Count,方案,ver,cdot,题解,sum,2x,choose,frac From： https://www.cnblogs.com/zifanoi/p/18038499