Description

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

Input

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

Output

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

Sample Input

1
1 3

Sample Output

1
7

Hint

样例说明

除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有2×2×2-1=7种方案。

数据范围

100%的数据中N和M均不超过100

50%的数据中N和M至少有一个数不超过8

30%的数据中N和M均不超过6

分析

首先想到，每一行最多只能塞进 2 门炮，否则就会出现隔山打牛的情况了，那么每一行就只有 2 种合法状态，即放 1 门炮和放 2 门炮

设 $f[i][j][k]$ 表示到了第 $i$ 行，有 $j$ 列只有一门炮，还有 $k$ 列有两门炮的方案数，显然 $k\leq m-j$

那么剩下没有放炮的列数就是：$m-j-k$，接下来可以有 3 种选择：

  1. 在第 $i$ 行不放炮，此时状态继承了上一行的状态，即 $f[i][j][k]=f[i-1][j][k]$

  2. 在第 $i$ 行放一门炮，又有两种选择（不能放在有 2 门炮的列上面）

    • 放在只有一门炮的一列，会使它变成有 2 门炮，因此 $k$ 的状态需要从 $k-1$ 转移过来，而只有一门炮的列数会减少 1，而变成当前的 $j$ ，所以 $j$ 的状态从 $j+1$ 转移过来，既然是从 $j+1$ 转移过来，那么可以在这 $j+1$ 列上放炮，方案数乘上 $j+1$，即：$f[i][j][k]+=f[i-1][j+1][k-1]\times (j+1)$
    • 放在没有炮的一列，会使它变成有 1 门炮，因此 $j$ 的状态要从 $j-1$ 转移，此时 $k$ 状态不变，又因为当前没有放炮的列数是 $m-j-k$，注意空的列数是相对于 $j=j-1$ 的状态而言的，所以实际空的列数为 $m-(j-1)-k$，即：$f[i][j][k]+=f[i-1][j-1][k]\times (m-(j-1)-k)$

  3. 在第 $i$ 行放两门炮，有三种情况需要讨论：

    • 两门炮都放在没放炮的那一列，和上面的的思路类似，但是注意这 2 门炮的排列组合，可以得出：$f[i][j]+=f[i-1][j-2][k]\times C^2_{m-(j-2)-k}$
    • 两门炮都放在放了 1 门炮的那一列，也是排列组合，可以得出：$f[i][j]+=f[i-1][j+2][k-2]\times C^2_{j+2}$
    • 一门放在没放炮的一列，一门放在放了炮的一列，此时综合情况 2 的两种子情况可以得出：$f[i][j][k]+=f[i-1][j][k-1]\times j \times (m-(k-1)-j)$

边界为 $f[0][0][0]=1$，这便是 省选 / NOI- 的 DP 题难度吧，题面不长但是很烧脑子。。。

Codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 108
using namespace std;
typedef long long ll;
int n,m; const int mod=9999973;
long long f[maxn][maxn][maxn];
int c(int x){
	return ((x*(x-1))/2)%mod;
}
long long dp(){
	f[0][0][0]=1;
	for(int i=1;i<=n;i++)	
		for(int j=0;j<=m;j++)
			for(int k=0;k<=(m-j);k++){
				f[i][j][k]=f[i-1][j][k];
                if(k>=1)(f[i][j][k]+=f[i-1][j+1][k-1]*(j+1));
                if(j>=1)(f[i][j][k]+=f[i-1][j-1][k]*(m-j-k+1));
                if(k>=2)(f[i][j][k]+=f[i-1][j+2][k-2]*(((j+2)*(j+1))/2));
                if(k>=1)(f[i][j][k]+=f[i-1][j][k-1]*j*(m-j-k+1));
                if(j>=2)(f[i][j][k]+=f[i-1][j-2][k]*c(m-j-k+2));
                f[i][j][k]%=mod;
			}
	long long ans=0;
	for(int i=0;i<=m;i++)
		for(int j=0;j<=m;j++)
			ans+=f[n][i][j],ans%=mod;
	return (ans+mod)%mod;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("testin.txt","r",stdin);
	freopen("testout.txt","w",stdout);
	#endif
	scanf("%d%d",&n,&m);
	printf("%lld",dp());
	return 0;
}