2023-08-12 18:06:37
发布于：广东
贝西和朋友们被抓获，并被困在远离农场的一个秘密大院里，贝西必须计划他们的逃跑！该院落由 N K NK 个保持单元组成，排列成 N × K N×K 矩形网格，水平和垂直相邻单元之间有门。每个牢房恰好容纳一头牛。
贝西已经侵入了系统，并且能够解锁任何门的子集，但每个门都有成本。为了让奶牛逃脱，贝西必须打开足够多的门，让所有奶牛都可以聚集在一个牢房中（这样它们就有足够的奶牛力量来挖掘地表！）。Bessie 希望最小化总解锁成本。
但赌注比以往任何时候都更高，贝西不能满足于只有一个逃跑计划：她需要后援。帮她数数最低成本的逃跑计划有多少种；如果其中一个计划中的某些门需要解锁，而另一个计划中不需要解锁，则两个计划被视为不同。
由于这个数字可能非常大，因此仅输出其模 10 9 + 7 109+7的余数。
输入格式（文件 Escape.In）：
第一行包含两个空格分隔的整数 N N 和 K K ( 2 ≤ N ≤ 30000 , 2 ≤ K ≤ 6 2≤N≤30000,2≤K≤6 )。接下来的 N N 行中的每一行都包含 K − 1 K−1 个 空格分隔的整数：解锁水平边缘上每个门的成本。
接下来的K K行中的每一行都 包含 N − 1 N−1 个 空格分隔的整数：解锁垂直边缘上每个门的成本。
所有费用均在 1 1 至 10 9 109之间 （含）。
在20%的测试用例中，保证 N ≤ 500 N≤500 ，并且所有权重在 1 1 和 5 5之间 （包括1 1 和5 5）。
在另外 20% 的测试用例中，保证 N ≤ 5000 N≤5000。
输出格式（文件 Escape.Out）：
单个整数：最小成本逃生计划的数量，模 10 9 + 7 109+7。
样本输入：
4 3
1 1
5 6
7 8
1 1
1 1 1
2 3 4
1 1 1
样本输出：
10
测试用例呈现一个 4x3 网格，
1 1
+-----+-----+
| | |
1 | |2 | 1
| 5 | 6 |
+-----+-----+
| | |
1 | |3 | 1
| 7 | 8 |
+-----+-----+
| | |
1 | |4 | 1
| | |
+-----+-----+
1 1
任何最小成本逃生计划都会使用成本 2 的门口、成本 3 的门口以及成本 1 的大约 9 个门口。对于不使用成本 1 的边有 10 个选择，因此答案是 10。
有帮助，赞一个