[HZOI 2016]我们爱数数
题目大意：
一张圆桌，每个位置按顺时针从(1)到(n)编号。有(n)个人，编号从(1)到(n)。如果编号为(i)的人坐到了编号为(i)的位置或坐到了与编号为(i)的位置相邻的位置，这个人就会感到开心，反之这个人会感到沮丧。求有多少种安排坐位的方法，使所有人都入座，并且使得至少(k)个人开心。
思路：
用(f_{i,j,s})表示前(i)个人，(j)个人开心，目前最后两个位置的状态为(s)的方案数。
枚举前两个人的位置，就可以化环为链，直接DP就可以求出(f)的值。
用(g_i)表示((n-i)!sum f_{i,j,s})，(g_i=sum {jchoose i}ans_j)。故(ans)可以通过(g_i)推出。
源代码：
#include<cstdio>
#include<cctype>
#include<cstring>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
typedef long long int64;
const int N=1001;
const int mod=1e9+7;
int p1[4]={0,0,1,2},p2[4]={0,1,2,3};
int n,m,fac[N],ifac[N],f[N][N][4],g[N];
bool v[N];
void exgcd(const int &a,const int &b,int &x,int &y) {
if(!b) {
x=1,y=0;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
inline int inv(const int &x) {
int ret,tmp;
exgcd(x,mod,ret,tmp);
return ((ret%mod)+mod)%mod;
}
inline int C(const int &n,const int &m) {
if(m>n) return 0;
return (int64)fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main() {
n=p1[1]=getint(),m=getint();
for(register int i=fac[0]=1;i<=n;i++) {
fac[i]=(int64)fac[i-1]*i%mod;
}
ifac[n]=inv(fac[n]);
for(register int i=n;i>=1;i--) {
ifac[i-1]=(int64)ifac[i]*i%mod;
}
for(register int i=0;i<4;i++) {
const int &a=p1[i];
v[a]=true;
for(register int j=0;j<4;j++) {
const int &b=p2[j];
if(a&&b&&a==b) continue;
v[b]=true;
memset(f,0,sizeof f);
f[2][(!!a)+(!!b)][(v[3]<<1)|v[2]]=1;
for(register int i=2;i<n;i++) {
for(register int j=0;j<=i;j++) {
for(register int k=0;k<4;k++) {
if(!f[i][j][k]) continue;
(f[i+1][j][k>>1]+=f[i][j][k])%=mod;
(f[i+1][j+1][2+(k>>1)]+=f[i][j][k])%=mod;
if(!(k&1)) (f[i+1][j+1][k>>1]+=f[i][j][k])%=mod;
if(!((k>>1)&1)) (f[i+1][j+1][1]+=f[i][j][k])%=mod;
}
}
}
const int t=((v[1]<<1)+v[n]);
for(register int i=1;i<=n;i++) {
for(register int k=0;k<4;k++) {
if(k&t) continue;
(g[i]+=(int64)f[n][i][k]*fac[n-i]%mod)%=mod;
}
}
v[b]=false;
}
v[a]=false;
}
for(register int i=n;i;i--) {
for(register int j=i+1;j<=n;j++) {
g[i]=((g[i]-(int64)g[j]*C(j,i)%mod)%mod+mod)%mod;
}
}
int ans=0;
for(register int i=m;i<=n;i++) (ans+=g[i])%=mod;
printf("%d
",ans);
return 0;
}