Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom10月前

12/25
09:58
一般动规与递推

[bzoj 1801] [Ahoi2009]chess 中国象棋

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮。 请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧.

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

一行包含两个整数N,M,中间用空格分开.

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

输出所有的方案数,由于值比较大,输出其mod 9999973

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

1 3

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

7

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

除了在3个格子中都放满炮的的情况外,其它的都可以.
100%的数据中N,M不超过100
50%的数据中,N,M至少有一个数不超过8
30%的数据中,N,M均不超过6

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

每行每列不能放超过2个棋子求方案数

设f[i][j][k]表示前i行,j列有1个棋子,k列有2个棋子的方案数

1、不放棋子

2、放1个在没有棋子的列上

3、放1个在有一个棋子的列上

4、放2个在没有棋子的列上

5、放1个在有一个棋子的列上,1个在没有棋子的列上

6、放2个在有一个棋子的列上

然后转移

 

[bzoj 1801] [Ahoi2009]chess 中国象棋