洛谷2051 [AHOI2009]中国象棋

题目链接

题意概述：n行m列棋盘放若干个棋子每行每列最多两个求方案总数，答案对9999973取模。

可以比较容易看出这是个dp，设f[i][j][k]表示前i行j列放1个棋子k列放2个棋子的方案总数。转移时分类讨论+计数就好了。分类讨论比较麻烦需要仔细考虑一下。

吐槽：我把循环里的m写成n还有50，查了半天（真的半天）取模QAQ

#include<cstring>

#include<iostream>

#include<cctype>

#include<cstdio>

#include<algorithm>

#define now f[i][j][k]

#define ll unsigned long long

using namespace std;

inline int read()

{

    register int X=;

    register char ch=;

    bool flag=;

    for(; !isdigit(ch); ch=getchar()) if(ch=='-') flag=;

    for(; isdigit(ch); ch=getchar()) X=(X<<)+(X<<)+ch-'';

    return (flag ? -X : X);

}

int N=;

const ll mod=;

int n,m;

ll f[][][],ans;

int C(int x)

{

    return x*(x-)/;

}

int main()

{

    n=read(),m=read(),f[][][]=;

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

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

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

            {

                if(now)

                {

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

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

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

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

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

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

                }

            }

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

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

            (ans+=f[n][i][j])%=mod;

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

}