중국 장기

제목의 대의.

\(n\) 행\(m\) 열의 바둑판 (\(1\leq n, m\leq 100\) 에서 줄마다 최대\(2\) 개의 바둑알을 넣을 수 있도록 하고, 프로젝트 수 $\bmod 9999973$를 구합니다.
 

문제풀이

   비교적 재미있는 dp.\(dp[I][i][j][k]\) 는 제\(1\) 줄에서 제\(I\) 줄로 표시하고\(i\) 열은\(1\) 바둑알만 있고\(j\) 열은\(2\) 바둑알만 있고\(k\) 열은\(0\) 바둑알만 있는 전체 방안 수를 설정할 수 있습니다.\(k\) 는\(m\) 와\(i\),\(j\) 에서 얻을 수 있으며, 이 부분을 제거할 수 있습니다.물론 스크롤 그룹으로 최적화할 수도 있다.   줄마다 최대\(2\)개의 바둑알을 놓을 수 있기 때문에 dp의 상태 이동 방정식은 최대\(5\)종의 상황만 각각 열거하면 된다. 구체적으로 아래의 코드를 보면 모두 이해할 수 있을 것이다.

#include 

#define MAX_N 100
#define MAX_M 100
#define MOD 9999973

using namespace std;

int n, m;
long long dp[MAX_N | 1][MAX_N | 1][2];
// i: 1     
// j: 2      
int ans;

inline int C(int x)
{
    return x * (x + 1) >> 1;
}

int main()
{
    cin >> n >> m;
    dp[0][0][1] = 1;
    dp[1][0][1] = m;
    dp[2][0][1] = C(m - 1);
    for(register int k = 2; k <= n; ++k)
    {
        for(register int i = 0; i <= m; ++i)
        {
            for(register int j = 0; i + j <= m; ++j)
            {
                dp[i][j][k & 1] = dp[i][j][k + 1 & 1];
                if(i) dp[i][j][k & 1] = (dp[i][j][k & 1] + dp[i - 1][j][k + 1 & 1] * (m - i - j + 1)) % MOD;
                if(i > 1) dp[i][j][k & 1] = (dp[i][j][k & 1] + dp[i - 2][j][k + 1 & 1] * C(m - i - j + 1)) % MOD;
                if(j) dp[i][j][k & 1] = (dp[i][j][k & 1] + dp[i + 1][j - 1][k + 1 & 1] * (i + 1)) % MOD;
                if(j > 1) dp[i][j][k & 1] = (dp[i][j][k & 1] + dp[i + 2][j - 2][k + 1 & 1] * C(i + 1)) % MOD;
                if(i && j) dp[i][j][k & 1] = (dp[i][j][k & 1] + dp[i][j - 1][k + 1 & 1] * i * (m - i - j + 1)) % MOD;
            }
        }
    }
    for(register int i = 0; i <= m; ++i)
    {
        for(register int j = 0; i + j <= m; ++j)
        {
            ans += dp[i][j][n & 1];
            // cout << m - i - j << " " << i << " " << j << ": " << dp[i][j][n & 1] << endl; // debug
            if(ans >= MOD) ans -= MOD;
        }
    }
    cout << ans;
    return 0;
}