题目描述
这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！
输入输出格式
输入格式：
一行包含两个整数N，M，之间由一个空格隔开。
输出格式：
总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。
输入输出样例
说明
样例说明
除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有2*2*2-1=7种方案。
数据范围
100%的数据中N和M均不超过100
50%的数据中N和M至少有一个数不超过8
30%的数据中N和M均不超过6
题解：
前30%明显是暴力
50%是状压，不过是3进制下的，不太好写...
一个明显的结论是不同的列（行）之间任意交换对答案是没有影响的。所以我们可以不用记录棋子防止的具体信息。我们设f[i][j][k]表示前i列有j列放了一个棋子、k列放了两个棋子的方案数。
那么再考虑这个状态能由哪些状态转移过来。
首先是第i列一个棋子也不放，那么f[i][j][k] = f[i-1][j][k]
其次是放一个，这时有两种情况；最后是放两个，有三种情况。请读者自己思考=-=
1 // f[i][j][k]表示前i行中有j列放了1个炮，k列放了两个炮的种类数 2 // f[i][j][k] = f[i-1][j][k] （一个都不放 3 // + f[i-1][j-1][k]*(m-j-k+1) + f[i-1][j+1][k-1]*(j+1) （放1个 4 // + f[i-1][j-2][k]*C(m-j-k+2,2) + f[i-1][j][k-1]*j*(m-j-k+1) + f[i-1][j+2][k-2]*C(j+2,2) （放2个 5 #include<iostream> 6 #include<cstdio> 7 #include<cstring> 8 #define LL long long 9 #define RI register int 10 #define KI 9999973 11 using namespace std; 12 const int INF = 0x7ffffff ; 13 const int N = 100 + 10 ; 14 15 inline int read() { 16 int k = 0 , f = 1 ; char c = getchar() ; 17 for( ; !isdigit(c) ; c = getchar()) 18 if(c == '-') f = -1 ; 19 for( ; isdigit(c) ; c = getchar()) 20 k = k*10 + c-'0' ; 21 return k*f ; 22 } 23 int n, m ; LL f[N][N][N] ; 24 25 inline LL C(int x,int y) { return (x*(x-1)>>1)%KI ; } // y都是2 26 int main() { 27 n = read(), m = read() ; 28 f[1][0][0] = 1 ; f[1][1][0] = m ; f[1][2][0] = C(m,2) ; 29 for(int i=2;i<=n;i++) { 30 for(int j=0;j<=m;j++) { 31 for(int k=0;k<=m-j;k++) { 32 f[i][j][k] = f[i-1][j][k] ; 33 if(j) f[i][j][k] += f[i-1][j-1][k]*(m-j-k+1), f[i][j][k] %= KI ; 34 if(k && j < m) f[i][j][k] += f[i-1][j+1][k-1]*(j+1), f[i][j][k] %= KI ; 35 if(j > 1) f[i][j][k] += f[i-1][j-2][k]*C(m-j-k+2,2), f[i][j][k] %= KI ; 36 if(k) f[i][j][k] += f[i-1][j][k-1]*j*(m-j-k+1), f[i][j][k] %= KI ; 37 if(k > 1 && j < m-1) f[i][j][k] += f[i-1][j+2][k-2]*C(j+2,2), f[i][j][k] %= KI ; 38 } 39 } 40 } 41 int ans = 0 ; 42 for(int j=0;j<=m;j++) { 43 for(int k=0;k<=m-j;k++) ans += f[n][j][k], ans %= KI ; 44 } 45 printf("%d",ans) ; 46 return 0 ; 47 }