BZOJ 4806 포(DP)

제목: n*m의 바둑판, (n, m<=100), 바둑판에 포를 놓고 포 사이에 서로 공격하지 않는 방안수. 
사고방식: n, m는 비교적 큰 형태로 T를 눌렀다.
열마다 포가 0개나 1개 또는 2개만 있을 수 있고, 열의 배치 위치는 상관없기 때문에 1개와 2개의 포를 놓는 열수를 기록하면 된다.
pp[i][j][k]는 전 i행에 j열이 1개, k열이 2개의 포가 있는 방안수를 나타낸다.
상태 전환:
dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k])%mod;//불발포 dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-1][k]*(m-(j-1)-k))))%mod;//포가 없는 곳에 dp[i][j][k]=(dp[i][j][k]+dp[i-1][j+1][k-1]*(j+1)))%mod를 넣는다//한 포에 dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-2][k]*C(m-k-(j-2)))))%mod 넣기;//포가 없는 곳에 dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k-1]*(m-j-(k-1)))*(j)))%mod 두 개 넣기;//포가 없는 곳과 포가 없는 곳에 각각 dp[i][j][k]=(dp[i][j][k]+dp[i-1][j+2][k-2]*C(j+2))%mod를 넣는다.//두 개의 포가 있는 곳에서 각각 한 개의 포를 쏘다
코드:

#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 105;
const int mod = 999983;
ll dp[maxn][maxn][maxn];

int C(int x)
{
    return x*(x-1)/2;
}

int main(void)
{
    int n, m;
    while(cin >> n >> m)
    {
        memset(dp, 0, sizeof(dp));
        dp[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++)
                {
                    dp[i][j][k] = (dp[i][j][k]+dp[i-1][j][k])%mod;  //   
                    if(j-1 >= 0) dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-1][k]*(m-(j-1)-k))%mod; //         
                    if(j+1 <= m && k-1 >= 0) dp[i][j][k] = (dp[i][j][k] + dp[i-1][j+1][k-1]*(j+1))%mod; //          
                    if(j-2 >= 0) dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-2][k]*C(m-k-(j-2)))%mod;    //         
                    if(k-1 >= 0) dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k-1]*(m-j-(k-1))*(j))%mod;   //                  
                    if(j+2 <= m && k-2 >= 0) dp[i][j][k] = (dp[i][j][k] + dp[i-1][j+2][k-2]*C(j+2))%mod;    //               
                }
        ll ans = 0;
        for(int i = 0; i <= m; i++)
            for(int j = 0; j+i <= m; j++)
                ans = (ans+dp[n][i][j])%mod;
        printf("%lld
", ans);
    }
    return 0;
}