【BZOJ1801】【AHOI2009】chess 中国象棋

Description

在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法。

Solution

很裸的DP吧。。

设$f_{i,j,k}$表示前$i$行、有$j$列放了一个、有$k$列放了两个。
分6种情况转移,具体看代码,应该非常好懂。

Source

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/****************************
* Au: Hany01
* Prob: BZOJ1801 & AHOI2009 中国象棋
* Date: Feb 3rd, 2018
* Email: hany01@foxmail.com
****************************/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define rep(i , j) for (int i = 0 , i##_end_ = j; i < i##_end_ ; ++ i)
#define For(i , j , k) for (int i = (j) , i##_end_ = (k) ; i <= i##_end_ ; ++ i)
#define Fordown(i , j , k) for (int i = (j) , i##_end_ = (k) ; i >= i##_end_ ; -- i)
#define Set(a , b) memset(a , b , sizeof(a))
#define SZ(a) ((int)(a.size()))
#define ALL(a) a.begin(), a.end()
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (9999973)
#define y1 wozenmezhemecaia
#ifdef hany01
#define debug(...) fprintf(stderr , __VA_ARGS__)
#else
#define debug(...)
#endif
inline void File() {
#ifdef hany01
freopen("bzoj1801.in" , "r" , stdin);
freopen("bzoj1801.out" , "w" , stdout);
#endif
}
template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
inline int read() {
register char c_; register int _ , __;
for (_ = 0 , __ = 1 , c_ = getchar() ; !isdigit(c_) ; c_ = getchar()) if (c_ == '-') __ = -1;
for ( ; isdigit(c_) ; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
return _ * __;
}
const int maxn = 105;
int n, m, dp[maxn][maxn], f[maxn][maxn][maxn], Ans;
inline int C2(int x) { return x * (x - 1) / 2; }
inline void mod(int &x) { if (x >= Mod) x -= Mod; }
int main()
{
File();
n = read(), m = read();
f[0][0][0] = 1;
For(i, 0, n - 1) For(j, 0, m) For(k, 0, m - j) if (f[i][j][k]) {
mod(f[i + 1][j][k] += f[i][j][k]);
mod(f[i + 1][j + 1][k] += f[i][j][k] * (LL)max(m - j - k, 0) % Mod);
mod(f[i + 1][j + 2][k] += f[i][j][k] * (LL)C2(m - j - k) % Mod);
if (j > 0) mod(f[i + 1][j - 1][k + 1] += f[i][j][k] * (LL)j % Mod);
if (j > 1) mod(f[i + 1][j - 2][k + 2] += f[i][j][k] * (LL)C2(j) % Mod);
mod(f[i + 1][j][k + 1] += f[i][j][k] * (LL)(m - j - k) % Mod * (LL)j % Mod);
}
For(j, 0, m) For(k, 0, m - j) mod(Ans += f[n][j][k]);
printf("%d\n", Ans);
return 0;
}
Contents
  1. 1. Description
  2. 2. Solution
  3. 3. Source