HDU 4832 Chess

思路：把行列的情况分别dp求出来，然后枚举行用几行，竖用几行，然后相乘累加起来就是答案
代码：

#include 
   
     #include 
    
      #include 
     
       using namespace std; typedef long long ll; const ll MOD = 9999991; const int N = 1005; int t, n, m, k, x, y; ll dp1[N][N], dp2[N][N], C[N][N]; int main() { for (int i = 0; i <= 1000; i++) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; j++) { C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD; } } int cas = 0; scanf("%d", &t); while (t--) { scanf("%d%d%d%d%d", &n, &m, &k, &x, &y); memset(dp1, 0, sizeof(dp1)); memset(dp2, 0, sizeof(dp2)); dp1[0][x] = dp2[0][y] = 1; for (int i = 1; i <= k; i++) { for (int j = 1; j <= n; j++) { if (j >= 2) dp1[i][j] = (dp1[i][j] + dp1[i - 1][j - 2]) % MOD; if (j >= 1) dp1[i][j] = (dp1[i][j] + dp1[i - 1][j - 1]) % MOD; dp1[i][j] = (dp1[i][j] + dp1[i - 1][j + 1]) % MOD; dp1[i][j] = (dp1[i][j] + dp1[i - 1][j + 2]) % MOD; } } for (int i = 1; i <= k; i++) { for (int j = 1; j <= m; j++) { if (j >




= 2) dp2[i][j] = (dp2[i][j] + dp2[i - 1][j - 2]) % MOD; if (j >= 1) dp2[i][j] = (dp2[i][j] + dp2[i - 1][j - 1]) % MOD; dp2[i][j] = (dp2[i][j] + dp2[i - 1][j + 1]) % MOD; dp2[i][j] = (dp2[i][j] + dp2[i - 1][j + 2]) % MOD; } } ll heng[N], shu[N]; memset(heng, 0, sizeof(heng)); memset(shu, 0, sizeof(shu)); for (int i = 1; i <= n; i++) for (int kk = 0; kk <= k; kk++) heng[kk] = (heng[kk] + dp1[kk][i]) % MOD; for (int i = 1; i <= m; i++) for (int kk = 0; kk <= k; kk++) shu[kk] = (shu[kk] + dp2[kk][i]) % MOD; ll ans = 0; for (int i = 0; i <= k; i++) { ans = (ans + (heng[i] * shu[k - i] % MOD) * C[k][i] % MOD) % MOD; } printf("Case #%d:\n", ++cas); cout << ans << endl; } return 0; }

HDU 4832(DP+计数问题)

HDU 4832 Chess