【题解】AHOI2009中国象棋

　　还记得第一次看见这题的时候好像还是联赛前后的事了，那时感觉这题好强……其实现在看来蛮简单的，分类讨论一下即可。题意非常的简单：每一行，每一列都不能超过两个棋子。考虑我们的dp，如果一行一行转移的话行上不能超过两个棋子是很好满足的，就看列上如何满足了。所以状态自然而然的设置为 \(f[i][j][k]\)，分别代表枚举到第 \(i\) 行，之前的列上有 \(j\) 列上有两个棋子，\(k\)列上有一个棋子时的方案数。

　　然后分情况转移乘以组合数即可。虽然简单，但感觉还是有所启发：做组合数类型的DP，应该观察到对后续状态真正产生影响的要素，只需保留这几样作为状态即可，其余的任选都有组合数来体现（其实一般的DP也是这样吧(｀・ω・´)）代码里面有小小注释……个人喜欢打英文的（主要是懒得切输入法）。

#include <bits/stdc++.h>

using namespace std;

#define maxn 200

#define int long long

#define mod 9999973

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

int C[maxn][];

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

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

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

    return x * k;

}

void up(int &x, int y) { x = (x + y % mod) % mod; }

void init()

{

    for(int i = ; i <= m; i ++) C[i][] = ;

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

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

            if(j > i) C[i][j] = ;

            else C[i][j] = C[i - ][j - ] + C[i - ][j];

}

signed main()

{

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

    f[][][] = ; init();

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

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

            for(int k = ; k <= m - j; k ++)

            {

                if(!f[i][j][k]) continue;

                up(f[i + ][j][k], f[i][j][k]); //

                int t = m - j - k, S = f[i][j][k];

                // place a chess

                if(t) up(f[i + ][j][k + ], S * t); // placed on a row of 0;

                if(k) up(f[i + ][j + ][k - ], S * k); // placed on a row of 1;

                // place two chess

                if(t >= ) up(f[i + ][j][k + ], S * C[t][]); //two on zero;

                if(k && t) up(f[i + ][j + ][k], S * t * k); // one on zero, one on one;

                if(k >= ) up(f[i + ][j + ][k - ], S * C[k][]); // two on one;

            }

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

        for(int k = ; k <= m - j; k ++)

            up(ans, f[n][j][k]);

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

    return ;

}