#CW47. 服务器方阵(square)

服务器方阵(square)

题目背景

小 W 负责检查一间矩形服务器机房。机房被划分为 rr 行 cc 列,每个格子至多放置一台服务器。为了避免过热,共享一条边的两台服务器不能同时运行。

题目描述

格子中的字符含义如下:

  • 0:没有服务器;
  • 1:有一台尚未开启的服务器;
  • 2:有一台已经开启的服务器。

小 W 不能关闭已经开启的服务器。她可以选择开启一些字符为 1 的服务器,但开启后任意两个边相邻的服务器都不能同时处于开启状态。

请计算最多可以新开启多少台服务器,并求达到这个最大数量的不同开启方案数。方案数对 998244353998244353 取模。

输入格式

第一行包含两个正整数 r,cr,c,满足 1≤r×c≤4001\le r\times c\le 400。

接下来 rr 行,每行包含一个长度为 cc 的字符串,仅由 0、1、2 组成。保证初始时任意两个字符为 2 的格子都不边相邻。

输出格式

输出两个整数 s,ws,w,其中 ss 是最多新开启的服务器数,ww 是达到 ss 的方案数对 998244353998244353 取模。

样例 1 输入

3 4
1210
0111
0020

样例 1 输出

1 1

样例 2 输入

2 3
111
101

样例 2 输出

3 1

子任务

本题采用子任务捆绑计分。只有该子任务中的全部测试数据均通过时,才能获得对应分数。

子任务 分值 测试点 限制
1 10 1∼21\sim 2 1≤r,c≤51\le r,c\le 5
2 30 3∼63\sim 6 r≤10r\le 10
3 10 7∼87\sim 8 每行至多有两个位置放置服务器
4 50 9∼209\sim 20 无额外限制

数据范围

所有测试数据均满足输入格式中的条件。服务器开启方案只记录哪些字符为 1 的格子被开启;字符为 0 的格子始终没有服务器,字符为 2 的格子始终保持开启。时限 5 秒。