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;
}