Card Arrangement
Time limit1sMemory limit128 MB
Given N cards and P pairwise greater-than constraints on k chosen positions forming a base-N number, compute the modular difference between the maximum and minimum valid values.
- Level
Hard8 of 10
- Topics
- Topological sort, Greedy, Graph
- Solved
- No attempts yet
Problem
There are N cards, each with one number written on it. The numbers are the integers from 0 to N-1, and no two cards have the same number.
Choose k cards and arrange them as C_{k-1}, C_{k-2}, ..., C_0. If this arrangement is interpreted as a base-N number, C_i is the digit in the N^i place, so the value is C_{k-1} × N^{k-1} + C_{k-2} × N^{k-2} + ... + C_0 × N^0.
The arrangement has constraints of the form C_i > C_j. This means that the number on the card placed at position i must be greater than the number on the card placed at position j. It is always true that i != j.
Given N, k, and the constraints, find the largest possible value and the smallest possible value among all valid arrangements, then output their difference.
Input
The first line contains three integers N, k, and P: the total number of cards, the number of cards to choose, and the number of constraints.
3 ≤ k ≤ N ≤ 300,000, 0 ≤ P ≤ 1,000,000
Each of the next P lines contains two integers a and b. This represents the constraint C_a > C_b.
Output
Output the difference between the largest and smallest values of valid card arrangements, modulo 1,000,000,007.
At least one valid arrangement always exists.