洛谷2051 [AHOI2009]中国象棋

题意

在 $N\times M$ 的棋盘上放若干个炮，要求不能互相攻击，求方案个数。

其中 $N,M\le 100$ 。

题解

将题意转化一下就是每行每列都不能放超过 $2$ 个棋子，那么可以用 $f[i][j][k]$ 表示前 $i$ 行，有 $j$ 列是有 $1$ 个棋子，有 $k$ 列是有 $2$ 个棋子的合法方案数。那么没有棋子的列数即为 $M-j-k$ 。

然后分类讨论。

不放

继承上一步的状态。

$$f[i][j][k]=f[i-1][j][k]$$

放一个

可以放在没有棋子的列或有 $1$ 个棋子的列，方案数为可以放的列的个数。

$$f[i][j][k]+=\begin{cases} f[i-1][j-1][k]\times (M-j-k+1) \\ f[i-1][j+1][k-1]\times (j+1) \end{cases}$$

放两个

可以都放在没有棋子或有 $1$ 个棋子的列上；也可以一个放在没有棋子的列上，一个放在有 $1$ 个棋子的列上。

前两种情况的方案数即为 $C^{2}_{x}$ ，$x$ 为可以放的列的个数。

$$f[i][j][k]+=\begin{cases} f[i-1][j-2][k]\times ((m-j-k+2)\times (m-j-k+1)\div 2) \\ f[i-1][j+2][k-2]\times ((j+2)\times (j+1)\div 2) \\ f[i-1][j][k-1]\times j\times (m-j-k+1) \end{cases}$$

代码

//f[i][j][k]前i行,有j列是有1个棋子,有k列是有2个棋子的合法方案数.

#include<bits/stdc++.h>
#define ha 9999973
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll n,m,ans,f[105][105][105];

int main()
{
    n=read(); m=read();
    f[0][0][0]=1;
    for (ll i=1;i<=n;i++)
    {
        for (ll j=0;j<=m;j++)
        {
            for (ll k=0;k<=m-j;k++)
            {
                f[i][j][k]=f[i-1][j][k];
                if (k>=1) f[i][j][k]+=f[i-1][j+1][k-1]*(j+1); //放1个在有1个的列上
                if (j>=1) f[i][j][k]+=f[i-1][j-1][k]*(m-j-k+1); //1;0
                if (j>=2) f[i][j][k]+=f[i-1][j-2][k]*((m-j-k+2)*(m-j-k+1)>>1); //2;0;0
                if (k>=2) f[i][j][k]+=f[i-1][j+2][k-2]*((j+2)*(j+1)>>1); //2;1;1
                if (k>=1) f[i][j][k]+=f[i-1][j][k-1]*j*(m-j-k+1); //2;0;1
                f[i][j][k]%=ha;
            }
        }
    }
    for (ll i=0;i<=m;i++) for (ll j=0;j<=m;j++) ans=(ans+f[n][i][j])%ha;
    printf("%lld",ans);
    return 0;
}