BZOJ 1801: [Ahoi2009]chess 中国象棋 [DP 组合计数]

时间：2022-11-13 22:51:33

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

在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法

100%的数据中N,M不超过100

容易发现每行每列最多两个

然后就不会了...看了别人的状态表示:

$f[i][j][k]$表示前$i$行有$j$列放了$1$个$k$列放了$2$个

因为只有那些行放了几个影响当前转移

然后转移自己随便写写就行了....注意$j$可能需要减

$1A$啦啦啦

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <set>

using namespace std;

typedef long long ll;

const int N=,P=;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m;

ll f[N][N][N];

inline int C2(int n){return n*(n-)/;}

void dp(){//printf("dp %d %d\n",m,n);

    f[][][]=;

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

        for(int j=;j<=n;j++)

            for(int k=;k<=n&&n-j-k>=;k++) if(f[i][j][k]){//printf("update %d %d %d\n",i,j,k);

                ll now=f[i][j][k];

                (f[i+][j][k]+=now)%=P;

                if(j<n) (f[i+][j+][k]+=now*(n-j-k))%=P;

                if(j>=) (f[i+][j-][k+]+=now*j)%=P;

                if(j+<=n) (f[i+][j+][k]+=now*C2(n-j-k))%=P;

                if(j>=&&k+<=n) (f[i+][j-][k+]+=now*C2(j))%=P;

                if(k<n) (f[i+][j][k+]+=now*(n-j-k)*j)%=P;

            }

    //for(int i=0;i<=m;i++) for(int j=0;j<=n;j++) for(int k=0;k<=n;k++) printf("f %d %d %d %lld\n",i,j,k,f[i][j][k]);

    ll ans=;

    for(int j=;j<=n;j++) for(int k=;k<=n;k++) ans=(ans+f[m][j][k])%P;//printf("hi %d %d %lld\n",j,k,f[m][j][k]);

    printf("%lld",ans);

}

int main(){

    freopen("in","r",stdin);

    m=read();n=read();

    if(n>m) swap(m,n);

    dp();

}

相关文章