https://www.luogu.org/problemnew/show/P2051

这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！

输入格式：

一行包含两个整数N，M，之间由一个空格隔开。

输出格式：

总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。

 

思路：

首先，明确一点：每行/列最多只能放2个炮，3个及以上一定会相互攻击。

一行一行来放，假如当前行放在i，j两列，则需要知道这两列是不是已经放了2个了，如果换两列k，l来放，有需要知道k，l两列是不是已经放了2个了，这样子很难去记录。

最后可耻地又去看了题解。洛谷排名第一的是__stdcall的题解，讲的很好：

棋子的顺序是无所谓的，并不需要准确知道当前棋盘的状态，

需要知道的仅仅是前面的所有行中，{放了2个炮的列有j列，放了1个炮的列有k列}，每一个这样子的状态有多少种情况。

然后在当前行中分类讨论怎么放，用加法原理和乘法原理转移。

这里面完全是组合数学的思想。

#include<bits/stdc++.h>
using namespace std;
#define C2(x) ((x)*((x)-1)/2)
#define C1(x) (x)
#define mod 9999973 
#define ll long long

int n,m,f[105][105][105];

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n>>m;
	f[0][0][0]=1;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			for(int k=0;k<=m;k++)
			{	/*这行不放*/
			    f[i+1][j][k]=(f[i+1][j][k]+f[i][j][k])%mod;
				/*放1个*/
  				if(j+1<=m&&k-1>=0)f[i+1][j+1][k-1]=(f[i+1][j+1][k-1]+(ll)f[i][j][k]*C1(k))%mod;
				if(k+1<=m)f[i+1][j][k+1]=(f[i+1][j][k+1]+(ll)f[i][j][k]*C1(m-j-k))%mod;
				/*放两个*/
				if(k-2>=0)f[i+1][j+2][k-2]=(f[i+1][j+2][k-2]+(ll)f[i][j][k]*C2(k))%mod;
				if(k+2<=m)f[i+1][j][k+2]=(f[i+1][j][k+2]+(ll)f[i][j][k]*C2(m-j-k))%mod;
				if(j+1<=m)f[i+1][j+1][k]=(f[i+1][j+1][k]+(ll)f[i][j][k]*C1(k)*C1(m-j-k))%mod;
			}
		}
	}
	int ans=0;
	for(int i=0;i<=m;i++)for(int j=0;j<=m;j++)ans=(ans+f[n][i][j])%mod;
	cout<<ans<<endl;
}