시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 31 | 28 | 24 | 88.889% |
There are n passengers in a single queue, waiting to enter the airplane. To avoid congestion, the queue should be partitioned into smaller parts. There are several ways to partition the queue. For instance, a queue of size 3 can be partitioned into1+2, 2+1, 1+1+1 or 3. It is easy to prove that there are 2n−1 ways to partition a queue of size n.
The problem becomes a little complicated, when we are not allowed to use parts whose sizes are in some given set S. For instance, if S is the set of even numbers, a queue of size 4 can be partitioned in 3 ways, namely 1+1+1+1, 1+3 and 3+1. You’re task is to count the number of ways to partition a queue of size n, with an additional condition that the size of no part should be in a given arithmetic sequence {m + ik|i = 0, 1, … } for the given m, k.
The first line of the input includes the number of test cases 1 ≤ t ≤ 10000. Each test case consists of three space separated integers n, m, k ( 1 ≤ n ≤ 30, 0 ≤ m < k < 30).
For each test case, print one line containing the answer to the question
3 10 0 2 15 1 4 28 3 7
55 235 18848806
ICPC > Regionals > Asia West Continent > Iran > Iran Internet Programming Contest > IIPC 2015 G번