2022年9月月赛乙组 T3.棋盘问题

2022年9月月赛乙组 T3.棋盘问题
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个 n×m 的棋盘，在上面放置若干个棋子，要求任一行任一列至多只能有两颗棋子，求一共有多少种放置方案。
由于方案数可能会很大，对方案数模 10^9+7。一只棋子都不放也算一种方案。
输入格式
两个整数表示 n 与 m
输出格式
单个整数：表示方案数模 10^9+7
数据范围
对于 20% 的数据，1≤n,m≤10
对于 100% 的数据，1≤n,m≤100
样例数据
输入:
2 3
输出:
49
输入:
1 3
输出:
7

题目解析：状态DP 分类讨论

#include 
using namespace std;
const int P=1e9+7;
long long dp[2][101][101][101];//滚动数组 做空间优化
int main()
{	
	int n,m;
	cin>>n>>m;
	//初始化dp[0]
	for(int x=0;x<=m;x++){
		for(int y=0;y<=m;y++){
			if(x+y>m) break;
			int z=m-x-y;
			dp[0][x][y][z]=1;
		}
	}
	//从dp[1]到dp[n]
	for(int i=1;i<=n;i++){
		for(int x=0;x<=m;x++){
			for(int y=0;y<=m;y++){
				if(x+y>m) break;
				int z=m-x-y;
				if(y+2*z>2*(n-i)) continue;
				int _i=i&1;
				int _isub1=(i-1)&1;
				//分类讨论：
				//1)第i行用了0个1   dp[i-1][x][y][z]
				dp[_i][x][y][z]=dp[_isub1][x][y][z];
				//2)第i行用了1个1   dp[i-1][x-1][y+1][z],dp[i-1][x][y-1][z+1]
				if(x) dp[_i][x][y][z]+=x*dp[_isub1][x-1][y+1][z];
				if(y) dp[_i][x][y][z]+=y*dp[_isub1][x][y-1][z+1];
				//3)第i行用了2个1
				if(x>1) dp[_i][x][y][z]+=x*(x-1)/2*dp[_isub1][x-2][y+2][z];
				if(y>1) dp[_i][x][y][z]+=y*(y-1)/2*dp[_isub1][x][y-2][z+2];
				if(x&&y) dp[_i][x][y][z]+=y*x*dp[_isub1][x-1][y][z+1];
				dp[_i][x][y][z]%=P;
				
			}
		}
	}
	//输出dp[n][m][0][0]
	cout<1][m][0][0];
	return 0;
}