[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 {j\choose 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\n",ans);

	return 0;

}