Time to Study Graphs with Chef
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Consider directed graph which has n + 2 layers numbered from left to right by integers from 0 up to n + 1. The leftmost (0) and the rightmost (n + 1) layers both contain only one vertex while every other layer contains exactly m vertices. Vertices are numbered independently in each layer by integers from 0 to m - 1. For each pair of vertices which are in the adjacent layers (i and i + 1 for any i (0 <= i <= n)), there exists an edge. The vertex which is in the layer with smaller number is the initial vertex for such edge and the other one is the terminal vertex.
Based on a graph as described above, Chef added k more edges. Each edge connects two vertices which are in the different layers, no matter the adjacent layers or not. Also, each edge is directed from left to right (as well as all previously existing edges).
Chef is interested in the number of ways to get from the leftmost layer to the rightmost one. Two paths are considered different if there is, at least, one edge which belongs to exactly one path. However, they are allowed to traverse the same set of vertices. In that case, there should be a multiple edge in the graph. It is also possible if some edge added by Chef connects two adjacent layers.
The first line of the input contains three space-separated integers: n, m and k.
k lines follow. Each of them describes one of the k additional edges and contains four space-separated integers edgei (where 0 <= i <= 3). First two integers are for the initial vertex and the other two - for the terminal one. Two integers each vertex is described by are the number of the layer (edge0 and edge2 respectively) and number of the vertex in its layer (edge1 and edge3 respectively).
Output a single integer: the number of ways to reach the last layer from the initial one modulo 109+7.
- 1 <= n <= 1012
- 1 <= m <= 105
- 0 <= k <= 5 * 104
- for each added edge:
- Layers: 0 <= edge0 < edge2 <= n+1
- Numbers inside the layer:
- In general: 0 <= edge1, edge3 <= m-1
- When edge0 = 0, edge1 = 0
- When edge2 = n + 1, edge3 = 0
- Subtask #1: n, m <= 6, k <= 2 (20 points)
- Subtask #2: n, m <= 110, k <= 30 (30 points)
- Subtask #3: original constraints (50 points)
Input: 4 2 2 2 1 5 0 0 0 4 0 Output: 19
Consider the graph without 2 edges added by Chef. There are 16 ways to get from the layer #0 to the layer #5. Now recall added edges. There are 2 ways to get from the layer #0 to the layer #5 using the edge 2 1 5 0 (0, 0 -> 1, 0 -> 2, 1 -> 5, 0 and 0, 0 -> 1, 1 -> 2, 1 -> 5, 0) and also 1 way to do it using the edge 0 0 4 0 (0, 0 -> 4, 0 -> 5, 0). Note, that there is no path traversing both added edges.
|Tags||combinatorics, dynamic-programming, feb15, graph, malinovsky239, medium|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.