记录编号	254416	评测结果	AAAAAAAAAA
题目名称	[HAOI 2016]放棋子	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.045 s
提交时间	2016-04-25 13:54:40	内存使用	19.00 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int ji=100000;
int n,m,i,j,k,w;
int dp[210][210][110];

void mul(int *x,int y){
	int i,j;
	for (j=1;j<=100;j++) x[j]*=y;
	for (j=1;j<=100;j++){
		x[j+1]+=x[j]/ji;
		x[j]%=ji;
	}
	return;
}
void getval(int x,int y){
	int i,j;
	for (i=1;i<=100;i++)
		dp[x][y][i]+=dp[x-1][y-1][i]*(x-y);
	if (y>=2){
		for (i=1;i<=100;i++)
			dp[x][y][i]+=dp[x-1][y-2][i]*(y-1);
	}
	for (i=1;i<=100;i++){
		dp[x][y][i+1]+=dp[x][y][i]/ji;
		dp[x][y][i]%=ji;
	}
	return;
}
void print(int *x){
	int i,j,w=100;
	while (x[w]==0&&w>0) w--;
	printf("%d",x[w]);
	for (i=w-1;i>0;i--)
	for (j=10000;j>0;j/=10){
		printf("%d",(x[i]/j)%10);
	}
	printf("\n");
	return;
}

int main(){
	freopen("chess_2016.in","r",stdin);
	freopen("chess_2016.out","w",stdout);
	scanf("%d",&n);
	if (n<=20){
		unsigned long long dp[210][210];
		dp[2][2]=dp[2][1]=1;
		dp[2][0]=2;
		for (i=3;i<=n;i++){
			for (j=0;j<=i;j++)
			if (j==0){
				dp[i][j]=1;
				for (k=1;k<=i;k++) dp[i][j]*=k;
			}
			else{
				dp[i][j]=(i-j)*dp[i-1][j-1];
				if (j>=2) dp[i][j]+=dp[i-1][j-2]*(j-1);
			}
			//cout<<dp[i][i]<<endl;
		}
		cout<<dp[n][n]<<endl;
		return 0;
	}
	
	for (i=1;i<=n;i++) dp[i][0][1]=1;
	dp[2][2][1]=dp[2][1][1]=1;
	for (i=1;i<=n;i++){
		for (j=1;j<=i;j++)
			mul(dp[i][0],j);
	}
	
	for (i=3;i<=n;i++){
		for (j=1;j<=i;j++)
			getval(i,j);
		//print(dp[i][i]);
	}
	
	print(dp[n][n]);
	return 0;
}