称(1sim n)排列的完美数 有多少个(i)满足(|P_i-i|=1)，求有多少个长度为(n)的完美数恰好为(m)的排列
因为恰好，容易想到二项式反演
令完美数恰好为(m)的排列数(G(m))，构造方案数，强行令(m)个位置完美，剩下的放任自流方案数为(F(m))，对于一种完美数为(M)的排列，在(F(m))中会被统计(large {Mchoose m})次
(large F(m)=sumlimits_{i=m}^n{ichoose m}G(i))
二项式反演(large G(m)=sumlimits_{i=m}^n(-1)^{i-m}{ichoose 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)=largesumlimits_{i=m}^n(-1)^{i-m}{ichoose m}(f[n][i][0]+f[n][i][1])*(n-i)!)