AHOI2091 中国象棋

原题链接:https://www.luogu.org/problem/P2051

收录于 NOI 系列题解集


思路

照例,暴力会炸。

由于每行每列不超过 2 枚棋子,考虑设计 DP。

dp(n, i, j) 表示前 n 行存在 i 列有且仅有一枚棋子,存在 j 列有且仅有两枚棋子。

这道题主要考验状态转移,详细见代码注释。

注意初值有三个,空棋盘也属于一种情形(惨痛教训),莫忘取模,开long long

这道紫题水得妙啊。

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>

const int MAXN = 105, MAXM = 105, MOD = 9999973;
int N, M;
long long dp[MAXN][MAXM][MAXM], ans;

inline int C(int n) {
  return n * (n - 1) >> 1;
}

int main() {
  scanf("%d%d", &N, &M);
  dp[1][0][0] = 1;
  dp[1][1][0] = M;
  dp[1][2][0] = C(M);
  for (int n = 2; n <= N; ++n) {
    for (int i = 0; i <= M; ++i) {
      for (int j = 0; i + j <= M; ++j) {
        // 不放棋子
        dp[n][i][j] += dp[n - 1][i][j];
        // 放一枚棋子
        if (i >= 1) dp[n][i][j] += (M - i - j + 1) * dp[n - 1][i - 1][j];
        if (j >= 1) dp[n][i][j] += (i + 1) * dp[n - 1][i + 1][j - 1];
        // 放两枚棋子
        if (i >= 2) dp[n][i][j] += C(M - i - j + 2) * dp[n - 1][i - 2][j];
        if (j >= 2) dp[n][i][j] += C(i + 2) * dp[n - 1][i + 2][j - 2];
        if (i >= 1 && j >= 1) dp[n][i][j] += (M - i - j + 1) * i * dp[n - 1][i][j - 1];
        
        dp[n][i][j] %= MOD;
      }
    }
  }
  ans = 0;
  for (int i = 0; i <= M; ++i) {
    for (int j = 0; i + j <= M; ++j) {
      ans += dp[N][i][j];
    }
  }
  ans %= MOD;
  printf("%lld\n", ans);
  return 0;
}
点赞

Leave a Reply