bzoj 1081 [Ahoi2009] chess 中国象棋

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1801

状态比较难设,的确没想到.

不关心第几列出现是否出现了棋子的个数.而是看看上一行第几列出现了1或2个棋子

利用组合巧妙解决问题.

设\(f[i][j][k]\)表示第i行有j列有1个棋子.有k行有2个棋子.

那么为空的即为\(m - j - k\)

状态转移方程:

1.这一行什么都不放:

\(f[i][j][k] += f[i - 1][j][k]\)

2.这一行放一个 在空行上放

\(f[i][j][k] += f[i - 1][j - 1][k] * (m - (j - 1) - k);\)

3.这一行放一个 在有一个棋子放

\(f[i][j][k] += f[i - 1][j + 1][k - 1] * (j + 1);\)

4.这一行放两个 都在一个棋子上放

\(f[i][j][k] += f[i - 1][j + 2][k - 2] * C(j + 2,2);\)

5.这一行放两个 在没有棋子上面放

\(f[i][j][k] += f[i - 1][j - 2][k] * C(m - j - k + 2,2);\)

6.这一行一个棋子在一个棋子的列上放,一个棋子在没有棋子的列上方

\(f[i][j][k] += f[i - 1][j][k - 1] * j * (m - j - k + 1)\)

边界的话:当然是\(f[0][0][0] = 1\)啦

滚动一下数组非常快

/*

卡常记录 ：

总耗时 : 111ms -> 86ms

最高用时 : 23ms -> 17ms

*/

#include <iostream>

#include <cstdio>

#define rep(i,x,p) for(register int i = x;i <= p;++ i)

#define sep(i,x,p) for(register int i = x;i >= p;-- i)

#define gc getchar()

#define pc putchar

const int maxN = 100 + 7;

const int mod = 9999973;

long long f[2][maxN][maxN];

int n,m;

inline int read() {

    int x = 0,f = 1;char c = gc;

    while(c < '0' || c > '9') {if(c == '-')f = -1;c = gc;}

    while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc;}

    return x * f;

}

inline int C(int n) {

    return n * ( n - 1 ) / 2;

}

int main() {

    f[0][0][0] = 1;

    int n,m;

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

    rep(i,1,n) {

    	int x = i % 2,q = x ? 0 : 1;

        rep(j , 0 , m) {

            for(register int k = 0;k + j <= m;++ k) {

                f[x][j][k] = f[q][j][k];

                if(j >= 1) f[x][j][k] += f[q][j - 1][k] * (m - (j - 1) - k);

                if(k >= 1) f[x][j][k] += f[q][j + 1][k - 1] * (j + 1);

                if(k >= 2) f[x][j][k] += f[q][j + 2][k - 2] * C(j + 2);

                if(j >= 2) f[x][j][k] += f[q][j - 2][k] * C(m - j - k + 2);

                if(k >= 1) f[x][j][k] += f[q][j][k - 1] * j * (m - j - k + 1);

                f[x][j][k] %= mod;

            }

        }

    }

    long long ans = 0,x = n % 2;

    rep(j , 0 , m) {

        for(register int k = 0;k + j <= m;++ k)

            ans += f[x][j][k];

        ans %= mod;

    }

    printf("%lld\n", ans);

    return 0;

}