Codeforces Round #175 (Div. 2) E Positions in Permutations
好题一枚，比赛的时候众神牛没几个能A出这道题，囧，，，
这里有个题解，我看了这个才懂的，包括下方的讨论 http://codeforces.com/blog/entry/7126
定义一个good position，如果一个位置是good的，则这个位置的数abs(p[i]-i)=1，也就是说i位置要么放i+1，要么放i-1.
现在问你长为N的排列有多少个排列恰好含有K个good position
由于每个位置要么放i-1 要么放i+1，所以可以设计这样的状态dp[i][j][a][b]，a b 分别表示 i i+1是否已经取过了，dp数组代表前i个位置取j个good position的取法
dp[n][i][j][k]就表示前n个取了i个good position，那么接下来的n-i个位置就可以随便放了，所以乘上(n-i)!就是good position 大于等于i个的排列数。
然后我们容斥一下去掉多余的数量，求出ans[i]，表示恰好有i个good position的排列数。
注意ans[i] != F[i] - F[i+1],（F[i]是大于等于i个good position的排列数），，因为F[i+1]可能在F[i]里面算了多次。这点有人在讨论里面说了。。
所以求ans[i]的时候，ans[i] =( F[i] - ans[j]*C[j][i])(对于所有的j>i),因为任意一种从j个good position取出i个的方法都被F[i]加过了
最后输出ans[K];
#include<cstdio>constint=1000000007;int[1010][1010][2][2];// first i digits contain j good position whether i i+1 is used or notvoidAdd(int&,int){+=;if(>=)-=;}longlong[1010];int[1010][1010];int(){int,;("%d%d",&,&);[0][0][1][0]=1;for(int=1;<=;++){for(int=0;<;++){for(int=0;<2;++){for(intnext=0;next<2;next++){if(!)Add([][+1][next][0],[-1][][][next]);if(<)Add([][+1][next][1],[-1][][][next]);Add([][][next][0],[-1][][][next]);}}}}for(int=0;<=;++)for(int=0;<=;++)[][]=?([-1][]+[-1][-1])%:1;for(int=0;<=;++){for(int=0;<2;++){for(int=0;<2;++){[]+=[][][][];[]%=;}}for(int=2;<=-;++)[]=[]*%;}for(int=;>=0;--){for(int=+1;<=;++){[]-=[]*[][];[]=([]%+)%;}}("%I64d\n",[]);return0;}