Bzoj1801: [Ahoi2009]chess 중국 장기: dp

제목 링크: [Ahoi 2009]chess 중국 장기
dp[i][j][k]를 설정하면 전 i행에 j열이 1개, k열이 2개의 포가 있음을 나타낸다. 상황에 따라 토론을 옮기면 한 줄에 최대 두 개의 포를 주의할 수 있다.

#include
#include
#include
#include
#define ll long long
using namespace std;
const int maxn=110;
const int mod=9999973;
ll dp[maxn][maxn][maxn];
int n,m;
ll c[maxn][maxn];

int main(){
	scanf("%d%d",&n,&m);
	c[0][0]=1;
	for (int i=1;i<=101;++i){
		c[i][0]=1;
		for (int j=1;j<=i;++j){
			c[i][j]=c[i-1][j]+c[i-1][j-1];
			if (c[i][j]>=mod) c[i][j]-=mod;
		}
	}
	for (int i=0;i<=2;++i) dp[1][i][0]=c[m][i];
	for (int i=2;i<=n;++i)
		for (int j=0;j<=m;++j)
			for (int k=0;k<=m-j;++k){
				for (int x=0;x<=2;++x){//      2
					int y=j+x;
					if (k+y<=m){
						dp[i][y][k]+=1ll*dp[i-1][j][k]*c[m-j-k][x];
						if (dp[i][y][k]>=mod) dp[i][y][k]%=mod;
					}
				}
				if (j>0&&k+1<=m){//   1        2
					dp[i][j-1][k+1]+=1ll*dp[i-1][j][k]*c[j][1];
					if (dp[i][j-1][k+1]>=mod) dp[i][j-1][k+1]%=mod;
				}
				if (j>1&&k+2<=m){//  2      2
					dp[i][j-2][k+2]+=1ll*dp[i-1][j][k]*c[j][2];
					if (dp[i][j-2][k+2]>=mod) dp[i][j-2][k+2]%=mod;
				}
				if (j+k+1<=m){//  2   1    2
					dp[i][j][k+1]+=1ll*dp[i-1][j][k]*c[j][1]*c[m-j-k][1];
					if (dp[i][j][k+1]>=mod) dp[i][j][k+1]%=mod;
				}
			}
	int ans=0;
	for (int i=0;i<=m;++i)
		for (int j=0;j<=m;++j){
		if (i+j>m) continue;
		ans+=dp[n][i][j];
		ans%=mod;
	}
	printf("%d",(ans+mod)%mod);
}