当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

5149:Sequence III

题目描述
Jinye is playing with cards. He has n cards in hand now. There is a number range from 1 to m writing on each card respectively.
There is a card sequence in the deck. At the beginning the sequence is empty.
Jinye will play for t rounds, at each round, Jinye will play one of these two operations:
1. select x y. x and y are both integer and x should between 1 and the number of cards in Jinye’s hand now, y should between 1 and the number of cards in the card sequence+1.That means Jinye insert the $x_{th}$ card in his hand into the card sequence’s $y_{th}$ position. For example, if the cards in Jinye’s hand is 2,3,3,6,1 now, and the card sequence is 2,2,5,4,3, after we play “select 4 2”, the cards in Jinye’s hand become 2,3,3,1, and the card sequence become 2,6,2,5,4,3.
2. pop. Pop up the cards in the card sequence’s right most and put it into the right most of Jinye’s hand. For example, if the cards in Jinye’s hand is 2,3,3,1 now, and the card sequence is 2,6,2,5,4,3, after we play “pop”, the cards in Jinye’s hand become 2,3,3,1,3 and the card sequence become 2,6,2,5,4.
The card sequence should be empty after t rounds.
For the card with number i writing on it, if it’s in card sequence now, its position in card sequence should never exceed $h_{i}$ at any moment.
There are some limits between cards. If x is limited by y, that means if there is at least one card with number y in the card sequence now, the card with number x can not be insert into the card sequence. Note that x can be equal to y, that means there is at most one x in the card sequence.
If there is no card can be insert into card sequence, the “select x y” operation is illegal.
If there is no card in the card sequence now, the “pop” operation is illegal.
Our problem is, how many legal operate sequence can meet all the demand.
Two operate sequences are consider different if there is a round they display different operations or there is a round they both display “select” but the parameters are different.
Output the answer modulo 1000000009.
输入解释
The first line contains a single integer T, indicating the number of test cases.
Each test case begin with three integers n, m, and t, indicating the number of cards in Jinye’s hand now, the range of the number writing on card, the number of rounds this game will play.
Next line contain n integers $A_{1},A_{2}, \ldots, A_{n}, A_{i}$ means the number writing on the $i_{th}$ cards.
Next line contain m integers $h_{1},h_{2}, \ldots, h_{m}$, as described above.
Next line contain an integers f, indicating the number of limits between cards.
Next f lines, each line contains two integers x and y, means x is limited by y.

[Technical Specification]
1 <= T <= 30
1 <= n <= 15
1 <= m <= 15
1 <= t <= 30,t is even
1 <= $A_{i}$ <= m
1 <= $h_{i}$ <= t
0 <= f <= m*m
1 <= x,y <= m
输出解释
For each case, output contain one line, the number of answer.
输入样例
1
1 1 2
1
1
0
输出样例
1
来自杭电HDUOJ的附加信息
Recommend heyang

该题目是Virtual Judge题目,来自 杭电HDUOJ

题目来源 BestCoder Round #23

源链接: HDU-5149

最后修改于 2020-10-25T23:20:13+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
6000/3000MS(Java/Others) 32768/32768K(Java/Others)