NEFU-1435 象棋之炮炮对决 (DP)

传送门

思路：按行dp，思考一下可以发现只需要知道有几列是已经有1个炮，有几列已经有两个炮，和顺序无关。

定义dp[i][j][k]为一共i行，j列有1个炮，k列有两个炮的方案数。

初始化dp[0][0][0]=1，一共有6种转移。不放，在0个炮的列放一个，在1个炮的列放一个，在0个炮的列放两个，在1个炮的列放两个，在0个炮的列放一个&在1个炮的列放一个。

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const long long MOD=9999973;
int n,m;
long long dp[101][101][101],ans;
inline long long C(long long a)
{
    return a*(a-1)/2;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        ans=0;
        memset(dp,0,sizeof(dp));
        dp[0][0][0]=1;
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<=m; j++)
            {
                for (int k=0; j+k<=m; k++)
                {
                    dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%MOD;
                    if (j+k<m)
                    {
                        dp[i+1][j+1][k]=(dp[i+1][j+1][k]+dp[i][j][k]*(m-j-k))%MOD;
                    }
                    if (j>0)
                    {
                        dp[i+1][j-1][k+1]=(dp[i+1][j-1][k+1]+dp[i][j][k]*j)%MOD;
                    }
                    if (j>1)
                    {
                        dp[i+1][j-2][k+2]=(dp[i+1][j-2][k+2]+dp[i][j][k]*C(j))%MOD;
                    }
                    if (m-j-k>=2)
                    {
                        dp[i+1][j+2][k]=(dp[i+1][j+2][k]+dp[i][j][k]*C(m-j-k))%MOD;
                    }
                    if (m-j-k>=1&&j>0)
                    {
                        dp[i+1][j][k+1]=(dp[i+1][j][k+1]+dp[i][j][k]*j*(m-j-k))%MOD;
                    }
                }
            }
        }
        for (int j=0; j<=m; j++)
        {
            for (int k=0; j+k<=m; k++)
            {
                ans=(ans+dp[n][j][k])%MOD;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}