Rockdu's Blog

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

1 3

7

说明

样例说明

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

数据范围

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

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

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

首先50%很好想，是一个状态压缩，考虑简化状态。

不难发现，一行一列最多只有2个棋子。

发现要计数和具体每一行每一列没有关系，如果记dp[i]为dp到第i列的状态，其实只需要记有多少行已经放了1个棋子，有多少行已经放了2个棋子就可以了。所以dp[i][j][k]表示dp到第i列，已经放了1个棋子的有j行，已经放了2个棋子的有k行，没放棋子的行数减出来就可以。这样就可以转移了。

转移有点恶心，想好了再写。

#include<cstdio>
#define LL long long
using namespace std;
const int maxn = 1e2 + 5;
const int mod = 9999973;
void Add(int &x, const int &a) {
    x += a; if(x >= mod) x -= mod;
}

int dp[maxn][maxn][maxn], n, m, ans;

int main() {
    scanf("%d%d", &n, &m);
    dp[0][0][0] = 1;
    for(register int i = 0; i <= m; ++i) {
        for(register int j = 0; j <= n; ++j)
            for(register int k = 0; k <= n - j; ++k) {
                //不放
                Add(dp[i + 1][j][k], dp[i][j][k]); 
                //一个棋子 
                if(j < n) Add(dp[i + 1][j + 1][k], 1ll * dp[i][j][k] * (n - j - k) % mod);
                if(k < n && j > 0) Add(dp[i + 1][j - 1][k + 1], 1ll * dp[i][j][k] * j % mod);
                //两个棋子 
                //放0, 1 
                if(k < n && j > 0 && j + k < n) Add(dp[i + 1][j][k + 1], (1ll * dp[i][j][k] * j % mod) * (n - j - k) % mod);
                //放1, 1 
                if(k < n - 1 && j > 1) Add(dp[i + 1][j - 2][k + 2], (1ll * dp[i][j][k] * ((1ll * (j - 1) * j / 2) % mod) % mod));
                //放0, 0 
                if(j + k < n - 1) Add(dp[i + 1][j + 2][k], (1ll * dp[i][j][k] * ((1ll * (n - j - k) * (n - j - k - 1) / 2) % mod) % mod));
            }
    }
    for(register int i = 0; i <= n; ++i)
        for(register int j = 0; j <= n; ++j)
            Add(ans, dp[m][i][j]);
    printf("%d", ans);
    return 0;
}