P2051 [AHOI2009]中国象棋

题目描述

这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好有一个棋子。你也来和小可可一起锻炼一下思维吧！

输入输出格式

输入格式：

一行包含两个整数N，M，之间由一个空格隔开。

输出格式：

总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。

说明

样例说明

除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有222-1=7种方案。

数据范围

100%的数据中N和M均不超过100

50%的数据中N和M至少有一个数不超过8

30%的数据中N和M均不超过6

一开始想打状压，但最后没时间了（校内开的考试）没打完，据说有50分。

对应状压的话，我们用两位来存储第i行是当前列已经存在几个炮。

分析一下发现，其实我们并不关注炮到底在哪里，只关心这一列有多少个（我感觉跟SDOI2010 地精部落有那么一点点的共同之处）

有时候，我们描述一个状态时，只关心其中某些的数量，而并不关系它的具体位置，转而用数学方法计算

用\(dp[i][j][k]\)代表目前到前i行所有列 0放j个（即有\(j\)列还没放炮） 1放k（有\(k\)列已经放了一个炮）个的方案数

转移方程在代码里。

Code：

#include <cstdio>

#define ll long long

const int N=104;

const int mod=9999973;

ll n,m,dp[N][N][N],ans=0;

//dp[i][j][k]代表前i行 所有列 0放j个 1放k个的方案数

int main()

{

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

    dp[0][m][0]=1;

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

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

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

            {

                dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k])%mod;//这排啥也不放

                if(k) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j+1][k-1]*(j+1))%mod;//一个0放1

                dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k+1]*(k+1))%mod;//一个1放2

                if(k>1) dp[i][j][k]=(dp[i][j][k]+(j+2)*(j+1)/2*dp[i-1][j+2][k-2])%mod;//双0放1

                dp[i][j][k]=(dp[i][j][k]+(k+2)*(k+1)/2*dp[i-1][j][k+2])%mod;//双1放2

                dp[i][j][k]=(dp[i][j][k]+dp[i-1][j+1][k]*(j+1)*k)%mod;//0,1各1

            }

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

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

            ans=(ans+dp[n][i][j])%mod;

    printf("%lld\n",ans);

    return 0;

}

2018.6.19

中国象棋

洛谷 P2051 [AHOI2009]中国象棋 解题报告