A787.Compound Escape--Platinum

NOI/NOI+/CTSC

USACO

通过率:0%

时间限制:2.00s

内存限制:256MB

题目描述

Bessie and friends have been captured and are trapped in a secret compound in
a location far from their farm, and it is up to Bessie to plan their escape!
The compound consists of NKNK holding cells arranged in an N×KN \times K
rectangular grid, where there are gates between horizontally and vertically
adjacent cells. Each cell houses exactly one cow.
Bessie has hacked into the system, and is able to unlock any subset of the
gates, but each gate has a cost. For the cows to escape, Bessie must open
enough gates that all the cows can gather in a single cell (so that they have
enough cow-power to tunnel to the surface!). Bessie wants to minimize the
total unlocking cost.
But the stakes are higher than ever, and Bessie cannot be content with just
one escape plan: she needs back-ups. Help her count the number of minimum-cost
escape plans; two plans are considered different if some gate needs to be
unlocked in one of the plans but not the other.
Since this number may be very large, only output its remainder modulo 109+710^9 + 7.

输入格式

The first line contains two space-separated integers, NN and KK (2N30000,2K62 \le N \le 30000, 2 \le K \le 6).
Each of the next NN lines contains K1K-1 space-separated integers: the costs
of unlocking each gate on a horizontal edge.
Each of the next KK lines contains N1N-1 space-separated integers: the costs
of unlocking each gate on a vertical edge.
All costs are between 11 and 10910^9 inclusive.
In 20% of the test cases, it is guaranteed that N500N \leq 500 and all weights
are between 11 and 55 inclusive.
In another 20% of the test cases, it is guaranteed that N5000N \leq 5000.

输出格式

A single integer: the number of minimum-cost escape plans, modulo 109+710^{9} + 7.

输入输出样例

  • 输入#1

    4 3
    1 1
    5 6
    7 8
    1 1
    1 1 1
    2 3 4
    1 1 1
    

    输出#1

    10
    

说明/提示

The test case presents a 4x3 grid,
1 1
+-----+-----+
| | |
1 | |2 | 1
| 5 | 6 |
+-----+-----+
| | |
1 | |3 | 1
| 7 | 8 |
+-----+-----+
| | |
1 | |4 | 1
| | |
+-----+-----+
1 1
Any minimum-cost escape plan will use the doorway of cost 2, the doorway of
cost 3, and some nine of the doorways of cost 1. There are ten choices for
which cost-1 edge to not use, so the answer is 10.

首页