← 返回比赛

已结束 GESP排位赛#13

← 上一题下一题 →

A4557 | $乌龟养殖场$

来源官方 / 2024

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

"Territory defines not just space, but peace; where balance is found by respecting the distance between." --- Macw 用钢丝网建造了一批同样大小的正方体网箱，将它们拼成了 $N\times M$ 的矩形网格（每个格子都是一个网箱）放在池塘里，专门用来养殖一种可爱的小乌龟。 乌龟生性温和，但它们有非常强烈的领地意识，如果他们的上下左右四个格子有乌龟，它们就会吵起架来。因此任意两只乌龟都不能相邻地放在一起。 Macw 在某些网箱里还安装了养殖设备，这些网箱里不能养小乌龟。 Macw 想知道，在至少养一只小乌龟的情况下，这组网箱一共有多少种可行的饲养方案。由于方案数量较大，输出的方案数量需要对 $10^9 +7$ 取模。 Problem credits: Macw07。

输入格式

输入包含多行，第一行输入两个整数 $N, M$，表示养殖场的大小。 接下来 $N$ 行，每一行输入 $M$ 个整数，整数之间以空格分隔开。 其中数字 1 代表水， 0 代表养殖设备。乌龟可以养殖在水中，但不能养殖在养殖设备中。

输出格式

输出一个整数，表示在至少养一只小乌龟的情况下的饲养方案数。请对 $10^9+7$ 取模。

输入输出样例

输入 #1

2 2
1 1
0 1

输出 #1

输入 #2

2 3
1 1 0
0 1 1

输出 #2

数据范围与约定： 对于100%的数据，保证 $1 \le N \le 500$。 对于100%的数据，保证 $1\le M \le 10$。 数据测试点规模约定如下： 测试点编号特殊约定1-5保证 $1 \le N \le 10$6-10保证 $80 \le N \le 100$11-25无特殊约定 样例解释： 对于第一个样例，养殖场的地形如下： 1101 养小乌龟一只的方案有 $3$ 种，分别是在每一个水域养殖一只；养 $2$ 只乌龟的方案有 $1$ 种，即在对角线处分别放置两只小乌龟。这个 $2\times 2$ 的矩形网格有 $4$ 种饲养方案，$4$ 对 $10^9+7$ 取模的结果是 $4$，因此输出 $4$。

C++ 编辑器

输入

输出