FillInTheGraph
2018 TCO Semi 1 · 2018-11-14 · by lg5293
Problem Statement
This problem has a non-standard time limit: 4 seconds.
You are given a directed graph with n nodes and m edges. The i-th edge goes from node a[i] to b[i]. Find the numbers of ways to complete the following task:
- Choose a number k between 1 and n, inclusive.
- Label each node in the graph with a number between 1 and k, inclusive.
- For each j from 1 to k-1, inclusive, there must exist an edge from a node with label j to a node with label j+1.
Two ways to complete the task are different if there exists a node that ends up with a different label.
Return the number of ways, modulo 10^9+7.
Constraints
- n will be between 1 and 15, inclusive.
- a will have between 1 and n*(n-1) elements, inclusive.
- a and b will have the same length.
- For all valid i, a[i] != b[i].
- All ordered pairs (a[i],b[i]) will be distinct.
3
{0,1,2}
{1,2,0}
Returns: 10
In this case, there are 10 valid colorings [1,1,1], [1,1,2], [1,2,1], [2,1,1], [1,2,2], [2,1,2], [2,2,1], [1,2,3], [2,3,1], [3,1,2]
5
{0,1,2}
{1,2,0}
Returns: 52
Note that the graph can be disconnected
2
{}
{}
Returns: 1
3
{2,1,0,1,2}
{1,0,1,2,0}
Returns: 11
15
{1,6,7,10,1,6,3,3,7,6,5,10,5,13,5,8,11,
12,9,5,13,10,4,0,6,12,12,12,6,11,7,8,9,
8,6,11,10,11,8,8,3,11,2,6,12,2,7,3,4,7,10}
{10,10,0,7,7,8,9,7,6,1,11,8,9,7,12,7,4,0,
11,6,0,6,11,11,11,9,1,10,2,0,10,4,3,2,9,
1,11,5,12,11,0,3,11,3,2,8,2,4,12,13,13}
Returns: 830203593
Submissions are judged against all 255 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FillInTheGraph with a public method int count(int n, vector<int> a, vector<int> b) · 255 test cases · 2 s / 256 MB per case