TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2099
  • 题目
  • P2099【状态压缩DP】奶牛的食物
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    奶牛们的牧草快要吃完了!FJ 听了贝茜的抱怨后,买了一块NM的牧场,牧场可以被分成NM个格子,有的格子很肥沃,适合放牧。 而有的很贫瘠,不适合放牧。 奶牛们的要求很苛刻,每只奶牛必须独占一个格子,并且任意两个奶 牛的格子不能相邻。
    FJ 要选出一些格子来放牧,他想知道,有多少种方案?

    输入格式

    第一行两个数 N,M.
    接下来 M 行,每行N 个数,每个数均为 0 或 1,0 表示不适合放牧,1 表示适合放牧。

    输出格式

    一个数,表示方案数,答案 mod 100000000 输出

    样例输入

    2 3
    1 1 1
    0 1 0

    样例输出

    9

    提示

    N≤12,M≤12