Cowmpetency
골드 II의견: 0
Farmer John is hiring a new herd leader for his cows. To that end, he has
interviewed \(N\) (\(2 \leq N \leq 10^9\)) cows for the position. After each
interview, he assigned an integer "cowmpetency" score to the candidate ranging from \(1\)
to \(C\) (\(1 \leq C \leq 10^4\)) that is correlated with their leadership
abilities.
Because he has interviewed so many cows, Farmer John has forgotten all of their
cowmpetency scores. However, he does remembers \(Q\)
(\(1 \leq Q \leq \min(N - 1, 100)\)) pairs of numbers \((a_i, h_i)\) where cow \(h_i\)
was the first cow with a strictly greater cowmpetency score than cows \(1\)
through \(a_i\) (so
\(1 \leq a_i < h_i \leq N\)).
Farmer John now tells you the \(Q\) pairs of \((a_i, h_i)\). Help him count how many
sequences of cowmpetency scores are consistent with this information! It is
guaranteed that there is at least one such sequence. Because this number may be
very large, output its value modulo \(10^9 + 7\).
Problem credits: Suhas Nagar
SCORING
- Inputs 3-4 satisfy \(N \leq 10\) and \(Q, C \leq 4\).
- Inputs 5-7 satisfy \(N, C \leq 100\).
- Inputs 8-10 satisfy \(N \leq 2000\) and \(C \leq 200\).
- Inputs 11-15 satisfy \(N, C \leq 2000\).
- Inputs 16-20 satisfy no additional constraints.
Problem credits: Suhas Nagar
The first line contains \(N\), \(Q\), and \(C\).
The next \(Q\) lines each contain a pair \((a_i, h_i)\). It is guaranteed that all
\(a_j\) are distinct.
The number of sequences of cowmpetency scores consistent with what Farmer John
remembers, modulo \(10^9+7\).
6 2 3
2 3
4 56The following six sequences are the only ones consistent with what Farmer John
remembers:
1 1 2 1 3 1
1 1 2 1 3 2
1 1 2 1 3 3
1 1 2 2 3 1
1 1 2 2 3 2
1 1 2 2 3 3
10 1 20
1 3399988086Make sure to output the answer modulo \(10^9+7\).
평가 및 의견
Cowmpetency
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Cowmpetency