洛谷P2051 [AHOI2009]中国象棋

题目描述
这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！
输入格式 一行包含两个整数N，M，之间由一个空格隔开。
输出格式 总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。
输入输出样例 输入 #1
复制
1 3 输出 #1
复制
7 说明/提示 样例说明
除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有222-1=7种方案。
数据范围
100%的数据中N和M均不超过100
50%的数据中N和M至少有一个数不超过8
30%的数据中N和M均不超过6
小骚题
f[i][j][k]表示到了第i行，有j列放一个炮，k列放两个炮的方法总数
然后暴力更新

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long 
using namespace std;
const int modd=9999973; 
int n,m;
int dp[105][105][105]; 
inline int cnm(int nn){
   return nn*(nn-1)/2%modd;}
inline int read(){
   
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
   ch=getchar();if(ch=='-')f=-1;}
	while(ch>='0'&&ch<='9'){
   x=x*10+ch-'0';ch=getchar();}
	return x*f; 
}
main(){
   
	n=read();m=read();
	dp[0][0][0]=1;
	for(int i=1;i<=n;i++){
   
		for(int j=0;j<=m;j++){
   
			for(int k=0;k+j<=m&&k+j<=2*i;k++){
   
				dp[i][j][k]+=dp[i-1][j][k];
				if(j>=1)dp[i][j][k]+=dp[i-1][j-1][k]*(m-j-k+1)%modd;//放一个 
				if(k>=1)dp[i][j][k]+=dp[i-1][j+1][k-1]*(j+1)%modd;//放一个 
			    if(k>=2)dp[i][j][k]+=dp[i-1][j+2][k-2]*cnm(j+2)%modd;//放两个在一个的
				if(k>=1)dp[i][j][k]+=dp[i-1][j][k-1]*j%modd*(m-j+1-k)%modd;//放两个一个一个一个空
				if(j>=2)dp[i][j][k]+=dp[i-1][j-2][k]*cnm(m-k-j+2)%modd; 
			}			
		}
	}
	int ans=0;
	for(int i=0;i<=m;i++){
   
		for(int j=0;i+j<=m&&(i+j)<=2*n;j++){
   
			ans+=dp[n][i][j]%modd;
		}
	}
	cout<<ans%modd;
	return 0;
}