P2051 [AHOI2009] 중국 장기

지식 포인트: DP

원제면

제목의 뜻을 약술하다.

\(N\times M\) 바둑판을 지정합니다.줄마다, 바둑알 수\(<3\) 의 방안 수를 구합니다.\(1\le N,M\le 100\).

문제의 뜻을 분석하다.

올바른 줄은 최대\(2\)개의 바둑알만 있고 바둑알 수\(<2\)의 열에만 놓을 수 있습니다.각 행이\(i\)행으로 열거될 때 바둑알의 수가 같은 두 열은 등가이며 바둑알의 위치는 영향을 주지 않는다.각 바둑알의 수를 매거하는 열수와 이\(2\)개의 바둑알의 위치를 고려하여 이동합니다.
설정\(f {i, j, k}\)는 앞\(i\)줄에\(j\)열에\(1\)개의 바둑알이 있고\(k\)열에 두 개의 바둑알이 있는 합법적인 방안 수를 나타낸다.분명히\(m-j-k\) 열이 있고 바둑알이 없습니다.
바둑돌의 수를 고려하다.
4

놓지 않을 때 공헌은\(f {i-1, j, k}\)입니다

4

하나 넣는 경우:
4

바둑알이 없는 열에 놓으면 바둑알이\(1\)의 열 수 + 1이 된다.\(m-(j-1)-k\)줄이 있고 바둑알이 없으면 이런 방치 방안이 있습니다.\(f {i-1, j-1, k}\times(m-(j-1)-k)\)로 공헌합니다.

4

바둑알이\(1\)인 열에 놓으면 바둑알이\(1\)인 열수-1, 바둑알이\(2\)인 열수+1이 된다.\(j+1\)종의 배치 방안이 있으면\(f {i-1,j+1,k-1}\times(j+1)\)에 기여합니다

4

두 개를 넣을 때:
4

모두 바둑알이 없는 열에 놓고\(f {i-1, j-2, k}\timesC((m-(j-2)-k), 2)\)로 공헌한다

4

모두\(1\)개의 바둑알이 있는 열에 놓고\(f {i-1,j+2,k-2}\timesC(j+2,2)\)에 공헌한다

4

한 개는 바둑알이 있는 열에 놓고, 한 개는\(1\)개의 바둑알이 있는 열에 놓는다.현재 바둑알 수가\(1\)인 열의 수는 변하지 않습니다.기여는\(f {i-1, j, k-1}\times j\times(m-(j-1)-k)\)이다

공헌구화, 즉\(f {i, j, k}\)의 값입니다.

코드 구현

//   :DP
/*
By:Luckyblock
*/
#include 
#include 
#include 
#define ll long long
const int kMaxn = 110;
const ll kMod = 9999973;
//=============================================================
ll n, m, ans, f[kMaxn][kMaxn][kMaxn];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
ll C(ll x, ll y) {
  return ((x - 1) * x / 2) % kMod;
}
//=============================================================
int main() {
  n = read(), m = read();
  f[0][0][0] = 1;
  for (int i = 1; i <= n; ++ i) {
    for (int j = 0; j <= m; ++ j) {
      for (int k = 0; j + k <= m; ++ k) {
        f[i][j][k] = f[i - 1][j][k];
        if (k >= 1) f[i][j][k] = (f[i][j][k] + f[i - 1][j + 1][k - 1] * (j + 1)) % kMod;
        if (j >= 1) f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][k] * (m - j + 1 - k)) % kMod;
        if (k >= 2) f[i][j][k] = (f[i][j][k] + f[i - 1][j + 2][k - 2] * C(j + 2, 2)) % kMod;
        if (j >= 2) f[i][j][k] = (f[i][j][k] + f[i - 1][j - 2][k] * C(m - j + 2 - k, 2)) % kMod;
        if (j >= 1 && k >= 1) f[i][j][k] = (f[i][j][k] + f[i - 1][j][k - 1] * j * (m - j - k + 1)) % kMod;
      }
    }
  }
  for (int j = 0; j <= m; ++ j) {
    for (int k = 0; j + k <= m; ++ k) {
      ans += f[n][j][k];
      ans %= kMod;
    }
  }
  printf("%lld", ans);
  return 0;
}