[AHOI2009] 中国象棋

分析

计数 DP

三进制状压 DP 可以拿 50 分

考虑到我们并不需要记录每一列的相对位置

定义 表示前 行中有 列放了 1 个棋子, 列放 2 个棋子的方方案数

采用刷表法,对于

  1. 在没有棋子的那一列放一枚棋子,有 种放法,答案累加到 .
  2. 同理,在有 1 枚棋子的那一列放一枚棋子,有 种放法,转移到 .
  3. 在没有棋子的列中选两列放棋子,有 种放法,转移到 .
  4. 在有 1 个棋子的列中选两列放棋子,有 种放法,转移到 .
  5. 在 1 个棋子和没有棋子的列中各选一列放棋子,有 种放法,转移到 .

最后累加答案即可

代码

#include<cstdio>
#define int long long
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
const int N=103,P=9999973;
int n,m,ans;
int f[N][N][N];
// 前 i 行,有 j 列放了 1 个棋子,k 列放了两个棋子的方案数
// 不考虑列之间的顺序
signed main(){
    scanf("%lld%lld",&n,&m);
    f[0][0][0]=1;
    FOR(i,0,n-1)FOR(j,0,m)FOR(k,0,m-j){
        f[i+1][j][k]=(f[i+1][j][k]+f[i][j][k])%P;// 不放
        if(m-j-k>0)f[i+1][j+1][k]=(f[i+1][j+1][k]+f[i][j][k]*(m-j-k))%P;// 放一个在 0
        if(j>0)f[i+1][j-1][k+1]=(f[i+1][j-1][k+1]+f[i][j][k]*j)%P;// 放一个在 1
        if(m-j-k>1)f[i+1][j+2][k]=(f[i+1][j+2][k]+f[i][j][k]*(m-j-k)*(m-j-k-1)/2)%P;
        if(j>1)f[i+1][j-2][k+2]=(f[i+1][j-2][k+2]+f[i][j][k]*j*(j-1)/2)%P;
        if(m-j-k>0&&j>0)f[i+1][j][k+1]=(f[i+1][j][k+1]+f[i][j][k]*(m-j-k)*j)%P;
    }
    FOR(j,0,m)FOR(k,0,m-j)ans=(ans+f[n][j][k])%P;
    printf("%lld",ans);
    return 0;
}

  转载请注明: Sshwy's Blog [AHOI2009] 中国象棋

 上一篇
[POJ1845]Sumdiv [POJ1845]Sumdiv
分析对 a 分解质因数: a=\prod_{i=1}^k{p_i}^{c_i}于是 a 的因数和表示为 \sigma_a=\prod_{i=1}^{k}\left(\sum_{j=0}^{c_i}{p_i}^j\right)括号里是一个
2018.11.24
下一篇 
[ZJOI2005] 午餐 [ZJOI2005] 午餐
分析DP& 贪心 首先贪心地想到,让吃饭时间长的先排队(邻项微扰证明) 定义 表示前 i 个人,1 号窗口打饭总时间为 时的最早吃完饭的时间。 当第 个人在 1 号窗口时,吃完饭的时间为 $max
2018.11.18
  目录