称\(1\sim n\)排列的完美数 有多少个\(i\)满足\(|P_i-i|=1\)，求有多少个长度为\(n\)的完美数恰好为\(m\)的排列
因为恰好，容易想到二项式反演
令完美数恰好为\(m\)的排列数\(G(m)\)，构造方案数，强行令\(m\)个位置完美，剩下的放任自流方案数为\(F(m)\)，对于一种完美数为\(M\)的排列，在\(F(m)\)中会被统计\(\large {M\choose m}\)次
\(\large F(m)=\sum\limits_{i=m}^n{i\choose m}G(i)\)
二项式反演\(\large G(m)=\sum\limits_{i=m}^n(-1)^{i-m}{i\choose m}F(i)\)，所以求\(F\)导出\(G\)
\(f[i][j][0/1][0/1]\)为前\(i\)个位置，选取\(j\)个完美位置，选或不选\(i+1\)，\(0\)是选
选\(i-1\)
\(f[i][j][0][0]+=f[i-1][j-1][0][0]\); \(f[i][j][1][0]+=f[i-1][j-1][0][1]\)
选择\(i+1\)
\(f[i][j][0][1]+=f[i-1][j-1][0][0]+f[i-1][j-1][1][0]\)
\(f[i][j][1][1]+=f[i-1][j-1][0][1]+f[i-1][j-1][1][1]\)
\(f[i][j][0][0]+=f[i-1][j][0][0]+f[i-1][j][1][0]\)
\(f[i][j][1][0]+=f[i-1][j][0][1]+f[i-1][j][1][1]\)
\(i=1\)和\(i=n\)
边界\(f[1][0][0][0]=1\) \(f[1][1][0][1]=1\)
\(i=n\)去掉\(i+1\)转移
\(F(m)=(f[n][n][0][0]+f[n][m][1][0])*(n-m)!\)
扔进反演式子就好
\(G(m)=\large\sum\limits_{i=m}^n(-1)^{i-m}{i\choose m}(f[n][i][0]+f[n][i][1])*(n-i)!\)
原文：https://www.cnblogs.com/shikeyu/p/13801402.html