#P17759. 点星

点星

题目描述

为寻找奶奶的踪影,MadelineMadeline 和 BadelineBadeline 跟随小鸟来到星空,她们发现星星排成 nn 行 mm 列的矩阵,其中一些星星亮着,MadelineMadeline 认为,只要将星星全部点亮就能找到奶奶。

MadelineMadeline 和 BadelineBadeline 可以分别选择若干位置进行点星:

  • MadelineMadeline 可以选择一个位置 (i,j)(i,j) ,消耗 ai,ja_{i,j} 的体力,将与第 ii 行第 jj 列星星相邻的星星改变状态。

  • BadelineBadeline 可以选择一个位置 (i,j)(i,j) ,消耗 bi,jb_{i,j} 的体力,将第 ii 行第 jj 列星星以及与它相邻的星星改变状态。

要求 1≤i≤n1 \le i \le n , 1≤j≤m1 \le j \le m ,每个人不会重复选择相同的位置。改变状态是指原本亮的星星变为不亮,原本不亮的星星变为亮着。

她们需要你求出最少消耗多少体力(两人消耗之和),才能将全部星星点亮,以及有多少种方案可以使消耗的总体力最少。

方案数对 2322^{32} 取模,两种方案不同当且仅当存在一个人在一种方案中选择了某位置而另一种没有。

输入格式

第一行两个整数 T,CT,C,表示数据组数及子任务编号。对于每组数据:

第一行两个整数 n,mn,m 。

接下来 nn 行,每行一个长度为 mm 的 0101 串,表示初始星星状态,00 表示亮着,11 表示不亮。

接下来 nn 行,每行 mm 个数表示 ai,ja_{i,j}。

接下来 nn 行,每行 mm 个数表示 bi,jb_{i,j}。

输出格式

对于每组测试数据,输出两个数,分别表示最少操作步数和方案数。

输入 #1

2 0
2 3
111
111
1 3 1
1 3 1
5 5 1
5 5 1

3 3
111
111
111
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

输出 #1

6 6
3 2

说明/提示

对于所有数据保证 T≤100T \le 100 , 2≤n,m≤122 \le n,m \le 12 , 0≤ai,j,bi,j≤1060 \le a_{i,j},b_{i,j} \le 10^6 。

对于每个测试点都存在两个参数 K,PK,P,满足该测试点的第 ii 组数据中 n,m≤max(P,K−i)n,m \le max(P,K-i) 。其中 K,PK,P 以及特殊性质见下表。

子任务 分值 n,m≤n,m \le K≤K\le P≤P\le 特殊性质
11 1010 33 44 33 无
22 44 55 44
33 2020 1010 1111 66
44 1212 1313 88 666×max(a)≤min(b)666 \times max(a) \le min(b)
55 ai,j=bi,ja_{i,j}=b_{i,j}
66 无

T2 序列变换(seq)3s 1G