炮(cannon)

炮(cannon)
【题目描述】
　　众所周知，双炮叠叠将是中国象棋中很厉害的一招必杀技。炮吃子时必须隔一个棋子跳吃，即俗称“炮打隔子”。 炮跟炮显然不能在一起打起来，于是rly一天借来了许多许多的炮在棋盘上摆了起来……他想知道，在N×M的矩形方格中摆若干炮（可以不摆）使其互不吃到的情况下方案数有几种。
　　棋子都是相同的。
【输入说明】
　　一行，两个正整数N和M。
【输出说明】
　　一行，输出方案数mod 999983。
【样例输入】
　　1 3
【样例输出】
　　7
【数据范围】
　　对于40%的数据,N<=4,M<=4
　　对于70%的数据,N<=100,M<=8
　　对于100%的数据,N<=100,M<=100

【题目分析】

　　DP。f[i][j][k]表示前i行放1个炮的有j列，放2个炮的有k（m-j）列。（每一行或者一列都是最多只能放两个炮）
　　1.该行不放炮;
　　2.该行在没有炮的1列中放置1个炮的方案数为 f[i-1][j-1][k]*(m-i-j+1);
　　3.该行在有1个炮的1列中放置1个炮（那这列就变成2个炮）的方案数为 f[i-1][j+1][k-1]*(j+1);
　　4.该行在没有炮的2列中各放置1个炮的方案数为 f[i-1][j-2][k]*C(m-j-k-2);
　　5.该行在有1个炮和没有炮的2列中各放置1个炮的方案数为 f[i-1][j][k-1]*(m-j-k+1)*j;
　　6.该行在有1个炮的2列中各放置1个炮的方案数为 f[i-1][j+2][k-2]*C(j+2,2);

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

const int mo=;

int m,n;

int ans=;

long long f[][][];

int C(int t)

{

    return ((t*(t-))>>)%mo;

}

int main()

{

    freopen("cannon.in","r",stdin);

    freopen("cannon.out","w",stdout);

    scanf("%d%d",&n,&m);

    f[][][]=;

    for (int i=;i<=n;i++)

        for (int j=;j<=m;j++)

            for (int k=;k<=m-j;k++)

            {

                f[i][j][k]=f[i-][j][k];

                if (j) f[i][j][k]=(f[i][j][k]+f[i-][j-][k]*(m-j-k+)%mo)%mo;

                if (k&&j<m) f[i][j][k]=(f[i][j][k]+f[i-][j+][k-]*(j+)%mo)%mo;

                if (j>) f[i][j][k]=(f[i][j][k]+f[i-][j-][k]*C(m-j-k+)%mo)%mo;

                if (j&&k) f[i][j][k]=(f[i][j][k]+f[i-][j][k-]*(m-j-k+)%mo*j%mo)%mo;

                if (k>&&j<m-) f[i][j][k]=(f[i][j][k]+f[i-][j+][k-]*C(j+)%mo)%mo;

            }

    for (int i=;i<=m;i++)

        for (int j=;j<=m-i;j++)

            ans=(ans+f[n][i][j])%mo;

    printf("%d",ans);

    fclose(stdin);fclose(stdout);

    return ;

}