BZOJ1801：[AHOI2009]中国象棋——题解

开发者一诺技术 2022年11月15日

0 收藏 425 点赞 4,722 浏览 1201 个字

http://www.lydsy.com/JudgeOnline/problem.php?id=1801

https://www.luogu.org/problemnew/show/P2051

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

我思维断掉了，秉承着dp试图自己做出来。

先想到dp方程有一维一定是处理到第几行，剩下的就是前几行的状态。

考虑状压……emm这100的大小状压可承受不起啊。

稍等，一列最多就两个炮啊！

我们完全可以用一种三维进制表示出每一列有多少个炮，这是是50%的做法。

正解延续了这个思想，显然我们只需要记住有多少列有0/1/2炮，经过奇妙的转移就能得到结果。

（然后斜挂不可避……）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p=;
int n,m;
ll f[][][];
int main(){
    scanf("%d%d",&n,&m);
    f[][][]=;
    for(int i=;i<n;i++){
    for(int j=;j<=m;j++){
        for(int k=;k+j<=m;k++){
        int l=m-j-k;
        f[i+][j][k]=(f[i+][j][k]+f[i][j][k])%p;
        if(l>)f[i+][j+][k]=(f[i+][j+][k]+f[i][j][k]*l)%p;
        if(j>)f[i+][j-][k+]=(f[i+][j-][k+]+f[i][j][k]*j)%p;
        if(l>)f[i+][j+][k]=(f[i+][j+][k]+f[i][j][k]*l*(l-)/)%p;
        if(l>&&j>)f[i+][j][k+]=(f[i+][j][k+]+f[i][j][k]*l*j)%p;
        if(j>)f[i+][j-][k+]=(f[i+][j-][k+]+f[i][j][k]*j*(j-)/)%p;
        }
    }
    }
    ll ans=;
    for(int j=;j<=m;j++){
    for(int k=;k+j<=m;k++){
        ans=(ans+f[n][j][k])%p;
    }
    }
    printf("%lld\n",ans);
    return ;
}