给定 n,m,k,和两个正整数序列 a1...n,b1...m,以及一个 k×k 的 01 矩阵 s1...k,1...k。
考虑一张有向图 G=(V,E),其中 V={S,T}∪({0,1}×([1,k]∩Z)2),而 E=E1∪E2∪E3 由三部分组成:
- E1={(S,(0,1,ai))∣1≤i≤n}∪{((1,k,bi),T)∣1≤i≤m}
- E2={((1,i,j),(0,i+1,j))∣1≤i<k,1≤j≤k}∪{(1,i,j),(0,i,j+1))∣1≤i≤k,1≤j<k}
- E3={((0,i,j),(1,i,j))∣1≤i,j≤k,si,j=1}
简单来说,你可以看成每个格子 (i,j),1≤i,j≤k 被拆成了一个入点 (0,i,j) 和一个出点 (1,i,j)。E1 描述了 S,T 与这些点之间的边,由 a,b 决定;E2 描述了每个格子的出点连向它上方和右方格子的入点的边;E3 描述了每个格子的入点连向出点的边,由 s 决定。
现在我们将 G 看成一个网络,每条边的容量是 1。你需要求出以 S 为源点,以 T 为汇点的最大流,以及最大流的数量(两个流被认为是不同的,当且仅当存在一条边在两个流中的流量不同)。
输入格式
第一行三个正整数 n,m,k。
第二行 n 个正整数 1≤a1<a2<...<an≤k。
第三行 m 个正整数 1≤b1<b2<...<bm≤k。
接下来 k 行,每行一个长度为 k 的 01 字符串,表示矩阵 s。
输出格式
输出一行两个非负整数,分别表示最大流和最大流的数量,后者对 109+7 取模。
数据范围与约定
对于全部数据,1≤n,m≤k≤400。
子任务编号 | n≤ | k≤ | 特殊性质 | 子任务分值 |
---|---|---|---|---|
1 | 7 | 7 | 无 | 5 |
2 | 18 | 18 | 无 | 5 |
3 | 10 | 400 | 无 | 10 |
4 | 100 | 400 | 无 | 25 |
5 | 400 | 400 | n=m 且最大流为 n | 10 |
6 | 400 | 400 | 最大流为 n | 25 |
7 | 400 | 400 | 无 | 20 |