#CW47. 服务器方阵(square)
服务器方阵(square)
题目背景
小 W 负责检查一间矩形服务器机房。机房被划分为 行 列,每个格子至多放置一台服务器。为了避免过热,共享一条边的两台服务器不能同时运行。
题目描述
格子中的字符含义如下:
0:没有服务器;1:有一台尚未开启的服务器;2:有一台已经开启的服务器。
小 W 不能关闭已经开启的服务器。她可以选择开启一些字符为 1 的服务器,但开启后任意两个边相邻的服务器都不能同时处于开启状态。
请计算最多可以新开启多少台服务器,并求达到这个最大数量的不同开启方案数。方案数对 取模。
输入格式
第一行包含两个正整数 ,满足 。
接下来 行,每行包含一个长度为 的字符串,仅由 0、1、2 组成。保证初始时任意两个字符为 2 的格子都不边相邻。
输出格式
输出两个整数 ,其中 是最多新开启的服务器数, 是达到 的方案数对 取模。
样例 1 输入
3 4
1210
0111
0020
样例 1 输出
1 1
样例 2 输入
2 3
111
101
样例 2 输出
3 1
子任务
本题采用子任务捆绑计分。只有该子任务中的全部测试数据均通过时,才能获得对应分数。
| 子任务 | 分值 | 测试点 | 限制 |
|---|---|---|---|
| 1 | 10 | ||
| 2 | 30 | ||
| 3 | 10 | 每行至多有两个位置放置服务器 | |
| 4 | 50 | 无额外限制 |
数据范围
所有测试数据均满足输入格式中的条件。服务器开启方案只记录哪些字符为 1 的格子被开启;字符为 0 的格子始终没有服务器,字符为 2 的格子始终保持开启。时限 5 秒。