银河美术馆-Beautyyu

这里是Beautyyu言醴的独立博客
越是孤单 越是向前 越是疲倦 越不能歇
——《未来的我》

AHOI2009中国象棋|题解

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

由于比较弱的缘故,稍微涉及数学的题目就做了很久..

设计状态$dp(k,n_{1},n_{2})$为考虑前k行时,设有$n_1$列放一个炮,$n_2$列放两个炮(剩下的列不放炮)时的所有方案数

若在第$k$行放置$0$个炮

$dp(k,n_1,n_2) += dp(k-1,n_1,n_2)$

若在第$k$行放置$1$个炮

  1. 放在只有$0$个炮的列上:$dp(k,n_1,n_2) += dp(k - 1,n_1 - 1,n_2)\times (第k-1行的n_0)$
  2. 放在只有$1$个炮的列上:$dp(k,n_1,n_2) += dp(k - 1,n_1 + 1,n_2 - 1)\times (第k-1行的n_1)$

若在第$k$行放置$2$个炮

  1. 两个炮放在只有$0$个炮的列上
  2. 两个炮放在只有$1$个炮的列上
  3. 一个炮放在有$0$个炮的列上,一个炮放在有$1$个炮的列上

具体转移与约束见下代码

注意到复杂度为$O(nm^2)$

所以当$m>n$时交换一下两者可能会快一些??

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define llint long long
using namespace std;
const llint base = 9999973;
llint dp[150][150][150];
int main (){
        int n,m;
        cin >> n >> m;
        dp[0][0][0] = 1;
        for (int i = 1;i <= n;++ i){
                for (int n1 = 0;n1 <= m;++ n1){
                        for (int n2 = 0;n2 <= m - n1;++ n2){
                                //put 0 pao 
                                dp[i][n1][n2] = dp[i - 1][n1][n2];
                                //put 1 pao
                                if(n1 > 0)
                                        dp[i][n1][n2] = (dp[i - 1][n1 - 1][n2] * (m - n1 + 1 -n2) % base + dp[i][n1][n2]) % base;
                                if(n2 > 0)
                                        dp[i][n1][n2] = (dp[i - 1][n1 + 1][n2 - 1] * (n1 + 1) % base + dp[i][n1][n2]) % base;
                                //put 2 pao
                                if(n1 > 1){
                                        int n0_ = m - n1 + 2 - n2;
                                        dp[i][n1][n2] = ((dp[i - 1][n1 - 2][n2] * (n0_ * n0_ - n0_) / 2) % base + dp[i][n1][n2]) % base;
                                }
                                if(n2 > 1){
                                        int n1_ = n1 + 2;
                                        dp[i][n1][n2] = ((dp[i - 1][n1_][n2 - 2] * (n1_ * n1_ - n1_) / 2) % base + dp[i][n1][n2]) % base;
                                }
                                if(n2 > 0 && n1 > 0){
                                        int n0_ = m - n1 + 1 - n2;
                                        dp[i][n1][n2] = (dp[i - 1][n1][n2 - 1] * (n1 * n0_) % base + dp[i][n1][n2]) % base;
                                }
                        }
                }
        }
        llint ans = 0;
        for (int i = 0;i <= m;++ i)
        for (int j = 0;j <= m - i;++ j)
        ans = (ans + dp[n][i][j]) % base;
        cout << ans;

        return 0;
}

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
如非注明,所有图片均来源于网络,如若侵删
Link to this article: https://blog.beautyyuyanli.ml/2018/07/23/2018-7-23-AHOI2009中国象棋题解/