BZOJ 1801 AHOI 2009 chess 중국 장기 DP

제목의 대의: 바둑판의 크기를 제시하고 임의의 줄과 열에 놓인 바둑알이 두 가지를 넘지 않는 몇 가지 방안을 묻는다.
사고방식: 비교적 번거로운 DP.f[i][j][k]는 앞의 i행으로 표시하고 한 바둑알의 열을 j로 하고 두 바둑알의 열을 k로 하는 방안수를 놓은 다음에 여섯 개의 이동이 있다.

f[i][j][k] = f[i - 1][j][k] 								//  
           + f[i - 1][j - 1][k] * (n - (j - 1) - k) + f[i - 1][j + 1][k - 1] * (j + 1)	//   
	   + f[i - 1][j - 2][k] * (n - (j - 2) - k) * (n - (j - 2) - k - 1)		//   0
	   + f[i - 1][j][k - 1] * (n - j - (k - 1)) * j					//   0  1
	   + f[i - 1][j + 2][k - 2] * (j + 2) * (j + 1)					//   1

f수조는 롱롱롱을 켜야 하며, 그렇지 않으면 폭발을 곱해야 한다.
전에 cf에서 나왔던 것 같아요.
CODE:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 110
#define MO 9999973
using namespace std;
 
int m,n;
long long f[MAX][MAX][MAX];
 
int main()
{
    cin >> m >> n;
    f[0][0][0] = 1;
    for(int i = 1; i <= m; ++i)
        for(int j = 0; j <= n; ++j)
            for(int k = 0; j + k <= n; ++k) {
                f[i][j][k] = f[i - 1][j][k];
                if(j - 1 >= 0)
                    f[i][j][k] += f[i - 1][j - 1][k] * (n - j - k + 1),f[i][j][k] %= MO;
                if(k - 1 >= 0) {
                    f[i][j][k] += f[i - 1][j + 1][k - 1] * (j + 1),f[i][j][k] %= MO;
                    f[i][j][k] += f[i - 1][j][k - 1] * (n - j - k + 1) * j,f[i][j][k] %= MO;
                }
                if(j - 2 >= 0)
                    f[i][j][k] += f[i - 1][j - 2][k] * (n - j - k + 2) * (n - j - k + 1) >> 1,f[i][j][k] %= MO;
                if(k - 2 >= 0)
                    f[i][j][k] += f[i - 1][j + 2][k - 2] * (j + 2) * (j + 1) >> 1,f[i][j][k] %= MO;
            }
    int ans = 0;
    for(int j = 0; j <= n; ++j)
        for(int k = 0; j + k <= n; ++k)
            ans = (ans + f[m][j][k]) % MO;
    cout << ans << endl;
    return 0;
}