中国像棋是什么？
\(dp_{i,j,k}\)表示前\(i\)行有\(j\)列有一个棋子，\(k\)列有两个棋子的方案数。
暴力大转移
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
// <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; } |
说点什么