题目描述

这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！

输入输出格式

输入格式

一行包含两个整数N，M，之间由一个空格隔开。

输出格式

总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。

样例

INPUT

1 3

OUTPUT

7

HINT

样例说明

除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有222-1=7种方案。

数据范围

100%的数据中N和M均不超过100

50%的数据中N和M至少有一个数不超过8

30%的数据中N和M均不超过6

SOLUTION

dp

本题我一开始想往状压上靠，对于每个状态，我们记一个类似于三进制的数来维护状态，但是由于数据范围十分的迷，100说大也不大，有的题\(10^7\)的都有（当然不是状压题），说大也大，100位的数怎么存怎么转移都是不好处理的问题。于是放弃思考直奔题解。

题解提示了一个重要的问题：和Brick game那题一样，本题对两行之间的状态转移并没有特殊要求，换句话说其实我们并不关心走到最后到底是哪些列没有炮，哪些列只有一个，哪些列只有两个，我们只关心到底有多少列没有炮，有多少列只有一个炮，有多少列有两个炮。而由于题目给出的限制，同一行最多只能新增两个炮，所以可以实现\(O(1)\)的转移。

所以我们可以考虑设dp数组为\(dp[i][j][k]\)表示第\(i\)行，前\(i\)行有\(j\)列含有一个炮，有\(k\)列含有2个炮。

所以转移可以是这样：

1. 本行放两个，全部放在原来为空不同两列；
2. 本行放两个，一个放在原有一个的某列，一个放在为空的某列；
3. 本行放两个，全部放在原有一个的不同两列；
4. 本行放一个，放在空列；
5. 本行放一个，放在原有一个的某列；
6. 本行不放炮。
   （我代码里也是按此顺序转移的，权当作是注释看吧）

由此题又可以发现，其实对于很多dp题，它们的优化往往会从优化状态转移入手，对于有多个状态转移方式的dp，应该考虑清楚这些具体状态是否必要，可否简化为一种抽象的状态，这种思路在的正解中也有体现，是一种比较好的思路。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long LL;const int N=110;const int P=9999973;int n,m;LL dp[N][N][N];inline LL C2(LL num) {LL ans=(num)*(num-1)/2;return ans;}int main(){    int i,j;    scanf("%d%d",&n,&m);    memset(dp,0,sizeof(dp));    dp[0][0][0]=1;     for (i=0;i
        
         1) dp[i+1][j+2][k]=(dp[i+1][j+2][k]+dp[i][j][k]*C2(m-j-k))%P;                if ((m-j-k>0)&&(j>0)) dp[i+1][j][k+1]=(dp[i+1][j][k+1]+dp[i][j][k]*(m-j-k)*(j)%P)%P;                if (j>1) dp[i+1][j-2][k+2]=(dp[i+1][j-2][k+2]+dp[i][j][k]*C2(j)%P)%P;                if (m-j-k>0) dp[i+1][j+1][k]=(dp[i+1][j+1][k]+dp[i][j][k]*(m-j-k)%P)%P;                if (j>0) dp[i+1][j-1][k+1]=(dp[i+1][j-1][k+1]+dp[i][j][k]*(j)%P)%P;                dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%P;            }        }    }    LL ans=0;    for (i=0;i<=m;++i)        for (j=0;(i+j)<=m;++j)            ans=(ans+dp[n][i][j])%P;    printf("%lld\n",ans);    return 0;}