F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 1801. -- [Ahoi2009]chess 中国象棋

1801: [Ahoi2009]chess 中国象棋

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 2801  Solved: 1721
[Submit][Status][Discuss]

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

Source

Day2

[Submit][Status][Discuss]

HOME Back