首页 > 其他分享 >NC19885 [AHOI2009]CHESS 中国象棋

NC19885 [AHOI2009]CHESS 中国象棋

时间:2022-09-04 03:55:06浏览次数:121  
标签:中国象棋 AHOI2009 geq cdot int CHESS 一个 dp mod

题目链接

题目

题目描述

在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧.一个炮要能攻击另一个炮他们必须要处于同一行或者一列且他们之间有且仅有一个棋子.

输入描述

一行包含两个整数N,M,中间用空格分开.

输出描述

输出所有的方案数,由于值比较大,输出其mod 9999973

示例1

输入

1 3

输出

7

备注

除了 \(3\) 个格子里都塞满了炮以外,其它方案都是可行的,所以一共有 \(2 \times 2 \times 2-1=7\) 种方案。
数据规模与约定
对于 \(30\%\) 的数据,\(n\) 和 \(m\) 均不超过 \(6\) 。
对于 \(50\%\) 的数据,\(n\) 和 \(m\) 至少有一个数不超过 \(8\) 。
对于 \(100\%\) 的数据,\(1 \leq n,m \leq 100\) 。

题解

知识点:计数dp,排列组合。

这道题是一个分类计数dp,考虑摆第 \(i\) 行时,需要且只要知道之前摆一个炮和摆两个炮的列数,不可能有摆超过两个炮的列,一行也不会有超过两个炮。刷表法免去边界问题,设 \(dp[i][j][k]\) 为摆第 \(i\) 行,放一个炮的有 \(j\) 列,放两个炮的有 \(k\) 列,分类讨论:

  1. 不放任何炮。转移方程:

    \[dp[i][j][k] = dp[i][j][k] + dp[i - 1][j][k] \]

  2. 放一个,可以选一个放了一个的列共 \(j\),也可以放在没有放的列 \(m-j-k\) 。转移方程:

    \[\left \{ \begin{array}{l} dp[i][j + 1][k] = dp[i][j + 1][k] + dp[i - 1][j][k] \cdot (m - j - k) &,m - j - k \geq 1\\ dp[i][j - 1][k + 1] = dp[i][j - 1][k + 1] + dp[i - 1][j][k] \cdot j &,j \geq 1 \end{array} \right. \]

  3. 放两个,可以选两个没有放的列有 \(C_{m-j-k}^2\) ,可以选两个放一个的列有 \(C_{j}^2\) ,可以一个选没有放的列一个选放一个的列有 \((m-j-k) \cdot j\) 。注意不能认为先放一个没有的列然后把这个算进放一个的列,这个包括了把两个同时放在一个没有选的列里面,会被一下行枚举到,所以不需要包括。转移方程:

    \[\left \{ \begin{array}{l} dp[i][j + 2][k] = dp[i][j + 2][k] + C_{m-j-k}^2 \cdot dp[i - 1][j][k]) &,m - j - k \geq 2\\ dp[i][j][k + 1] = dp[i][j][k + 1] + dp[i - 1][j][k] \cdot (m - j - k) \cdot j &,j \geq 1\\ dp[i][j - 2][k + 2] = dp[i][j - 2][k + 2] + C_{j}^2 \cdot dp[i - 1][j][k] &,j \geq 2 \end{array} \right. \]

时间复杂度 \(O(nm^2)\)

空间复杂度 \(O(nm^2)\)

代码

#include <bits/stdc++.h>

using namespace std;

const int mod = 9999973;
int dp[107][107][107];

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    dp[0][0][0] = 1;
    for (int i = 1;i <= n;i++) {
        for (int j = 0;j <= m;j++) {
            for (int k = 0;j + k <= m;k++) {
                ///一个也不放
                dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k]) % mod;

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

                ///放两个
                if (m - j - k >= 2) dp[i][j + 2][k] = (dp[i][j + 2][k] + 1LL * (m - j - k) * (m - j - k - 1) / 2 % mod * dp[i - 1][j][k]) % mod;
                if (m - j - k >= 1 && j >= 1) dp[i][j][k + 1] = (dp[i][j][k + 1] + 1LL * (m - j - k) * j % mod * dp[i - 1][j][k]) % mod;///不能先摆一个得到j+1列一个子再摆另一个,因为被包括在全放在没有子的情况里了
                if (j >= 2) dp[i][j - 2][k + 2] = (dp[i][j - 2][k + 2] + 1LL * j * (j - 1) / 2 % mod * dp[i - 1][j][k]) % mod;
            }
        }
    }
    int ans = 0;
    for (int i = 0;i <= m;i++) {
        for (int j = 0;i + j <= m;j++) {
            ans = (ans + dp[n][i][j]) % mod;
        }
    }
    cout << ans << '\n';
    return 0;
}

标签:中国象棋,AHOI2009,geq,cdot,int,CHESS,一个,dp,mod
From: https://www.cnblogs.com/BlankYang/p/16654174.html

相关文章

  • CF1545B AquaMoon and Chess(要不再看一下?)
    题目大意:你有一个长为\(n\)的棋盘,这个棋盘上有一些棋子,你可以进行如下操作:如果第\(i+2\)个位置是空的,且第\(i+1\)个位置非空,则可以将第ii个位置的棋子......
  • CF559C Gerald and Giant Chess
    GeraldandGiantChessCF599C(Luogu)题面翻译给定一个H*W的棋盘,棋盘上只有N个格子是黑色的,其他格子都是白色的。在棋盘左上角有一个卒,每一步可以向右或者向下移动一格......