【BZOJ1801】【AHOI2009】中国象棋

~~中国像棋是什么？~~

\(dp_{i,j,k}\)表示前\(i\)行有\(j\)列有一个棋子，\(k\)列有两个棋子的方案数。

暴力大转移

// <1801.cpp> - 01/10/17 08:55:54
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=100001;
const int N=110;
const int INF=1e9;
const int MOD=9999973;
int dp[N][N][N];
int main(){
    int n=gi(),m=gi();
    dp[0][0][0]=1;
    for(int i=0;i<n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=m-j;k++){
                (dp[i+1][j][k]+=dp[i][j][k])%=MOD;
                if(j)(dp[i+1][j-1][k+1]+=j*dp[i][j][k])%=MOD;
                if(j>1)(dp[i+1][j-2][k+2]+=(1ll*j*(j-1)*dp[i][j][k]>>1)%MOD)%=MOD;
                (dp[i+1][j+1][k]+=(m-j-k)*dp[i][j][k])%=MOD;
                (dp[i+1][j+2][k]+=(1ll*(m-j-k)*(m-j-k-1)*dp[i][j][k]>>1)%MOD)%=MOD;
                (dp[i+1][j][k+1]+=(1ll*(m-j-k)*j*dp[i][j][k]%MOD))%=MOD;
            }
    int ans=0;
    for(int j=0;j<=m;j++)
        for(int k=0;k<=m-j;k++)(ans+=dp[n][j][k])%=MOD;
    printf("%d",ans);
    return 0;
}

// <1801.cpp> - 01/10/17 08:55:54

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=100001;

const int N=110;

const int INF=1e9;

const int MOD=9999973;

int dp[N][N][N];

int main(){

int n=gi(),m=gi();

dp[0][0][0]=1;

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

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

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

(dp[i+1][j][k]+=dp[i][j][k])%=MOD;

if(j)(dp[i+1][j-1][k+1]+=j*dp[i][j][k])%=MOD;

if(j>1)(dp[i+1][j-2][k+2]+=(1ll*j*(j-1)*dp[i][j][k]>>1)%MOD)%=MOD;

(dp[i+1][j+1][k]+=(m-j-k)*dp[i][j][k])%=MOD;

(dp[i+1][j+2][k]+=(1ll*(m-j-k)*(m-j-k-1)*dp[i][j][k]>>1)%MOD)%=MOD;

(dp[i+1][j][k+1]+=(1ll*(m-j-k)*j*dp[i][j][k]%MOD))%=MOD;

}

int ans=0;

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

for(int k=0;k<=m-j;k++)(ans+=dp[n][j][k])%=MOD;

printf("%d",ans);

return 0;

}