1801: [Ahoi2009]chess 中国象棋

1801: [Ahoi2009]chess 中国象棋

Time Limit: 10 Sec   Memory Limit: 64 MB Submit: 1391   Solved: 802 [ 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

Day2

[ Submit][ Status][ Discuss] dpdpdp 记f[i][j][k]:放了i行  其中放了j列是只有一个炮的k列有两个炮的 转移方程就不难写出 最后统计下f[n][i][j]就好 GG(组合数写错了，好蠢啊) #include<iostream> #include<cstdio> #include<queue> #include<vector> #include<bitset> #include<algorithm> #include<cstring> #include<map> #include<stack> #include<set> #include<cmath> #include<ext/pb_ds/priority_queue.hpp> using namespace std; typedef long long LL; const LL mo = 9999973; const int maxn = 110; int n,m; LL f[maxn][maxn][maxn],C[maxn][maxn]; int main() { #ifdef DMC freopen("DMC.txt","r",stdin); #endif C[0][0] = 1; cin >> n >> m; for (int i = 1; i <= max(n,m); i++) { C[i][0] = 1; for (int j = 1; j <= i; j++) C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mo; } 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; k++) { if (j + k > m) break; if (i == 1 && k) break; f[i][j][k] = f[i-1][j][k]; //if (k) f[i][j][k] = (f[i][j][k] + f[i-1][j+1][k-1])%mo; //if (j) f[i][j][k] = (f[i][j][k] + f[i-1][j-1][k])%mo; //if (j >= 2) f[i][j][k] = (f[i][j][k] + f[i-1][j-2][k])%mo; //if (k) f[i][j][k] = (f[i][j][k] + f[i-1][j][k-1])%mo; //if (j < m-1 && k >= 2) f[i][j][k] = (f[i][j][k] + f[i-1][j+2][k-2])%mo; if (k) f[i][j][k] = (f[i][j][k] + C[j+1][1]*f[i-1][j+1][k-1])%mo; if (j) f[i][j][k] = (f[i][j][k] + C[m-j-k+1][1]*f[i-1][j-1][k])%mo; if (j >= 2) f[i][j][k] = (f[i][j][k] + C[m-j-k+2][2]*f[i-1][j-2][k])%mo; if (k) f[i][j][k] = (f[i][j][k] + C[m-j-k+1][1]*C[j][1]%mo*f[i-1][j][k-1])%mo; if (j < m-1 && k >= 2) f[i][j][k] = (f[i][j][k] + C[j+2][2]*f[i-1][j+2][k-2])%mo; } LL ans = 0; for (int j = 0; j <= m; j++) for (int k = 0; k <= m; k++) { if (j + k > m) break; ans = (ans + f[n][j][k])%mo; } cout << ans; return 0; }