BZOJ 1801: [Ahoi2009]chess 中国象棋( dp )

BZOJ 1801: [Ahoi2009]chess 中国象棋( dp )

dp(i, j, k)表示考虑了前i行, 放了0个炮的有j列, 放了1个炮的有k列. 时间复杂度O(NM^2)

--------------------------------------------------------------------------

#include<cstdio>
#include<cstring>
#include<algorithm>
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 109;
const int MOD = 9999973;
const int INV = 4999987;
 
int n, m;
int dp[maxn][maxn][maxn];
 
inline void upd(int &x, int t) {
if((x += t) >= MOD)
x -= MOD;
}
 
int main() {
scanf("%d%d", &n, &m);
memset(dp, 0, sizeof dp);
dp[0][m][0] = 1;
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
for(int k = 0; k <= m - j; k++) {
int &t = dp[i][j][k];
upd(t, dp[i - 1][j][k]);
if(k) upd(t, (j + 1) * dp[i - 1][j + 1][k - 1] % MOD);
upd(t, (k + 1) * dp[i - 1][j][k + 1] % MOD);
if(k >= 2) upd(t, ll(INV) * (j + 1) * (j + 2) * dp[i - 1][j + 2][k - 2] % MOD);
upd(t, ll(INV) * (k + 1) * (k + 2) * dp[i - 1][j][k + 2] % MOD);
upd(t, ll(k) * (j + 1) * dp[i - 1][j + 1][k] % MOD);
}
int ans = 0;
for(int i = 0; i <= m; i++)
for(int j = 0; j <= m - i; j++)
upd(ans, dp[n][i][j]);
printf("%d\n", ans);
return 0;
}

--------------------------------------------------------------------------

1801: [Ahoi2009]chess 中国象棋

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 1172  Solved: 688
[Submit][Status][Discuss]

Description

在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧.

Input

一行包含两个整数N,M,中间用空格分开.

Output

输出所有的方案数,由于值比较大,输出其mod 9999973

Sample Input

1 3

Sample Output

7

HINT

除了在3个格子中都放满炮的的情况外,其它的都可以.

100%的数据中N,M不超过100
50%的数据中,N,M至少有一个数不超过8
30%的数据中,N,M均不超过6

Source

上一篇:NYOJ题目28大数阶乘


下一篇:Asp.net中前台javascript与后台C#交互