P2051 [AHOI2009]中国象棋

    • 714通过
    • 1.6K提交
  • 题目提供者 shengmingkexue
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 状态压缩,状压 递推 各省省选 2009 安徽
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    输入输出格式

    输入格式:

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    1 3
    输出样例#1: 复制
    7

    说明

    样例说明

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

    数据范围

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

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

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。