410703: GYM104081 D Devil May Cry

Memory Limit:512 MB Time Limit:10 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Devil May Crytime limit per test10 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

​在 YahAHa 很喜欢的游戏《Devil May Cry》系列中,有一个角色 Dante ,拥有非常多的武器和招式。举例来说,在《Devil May Cry 5》中,Dante 有六把近战武器,六把远程武器,四种战斗风格,三种战斗形态。

每种武器,风格和战斗形态,都将赋予 Dante 不同的技能,因此,Dante拥有极为丰富的技能(超过200!),利用这些丰富的技能,你可以打出各种各样的花式连招。

现在,YahAHa 想要设计一些Dante的连招,连招由若干个依次释放的技能组成,假如在某个连招中一共释放了 $$$n$$$ 个技能,则这个连招可以描述成一个下标从 $$$1$$$ 开始的长度为 $$$n$$$ 的数列 $$$a$$$ ,数列中的每个项都是一个正整数,代表一个技能。

一个合法的连招要满足如下条件:

- YahAHa 只想用 $$$m$$$ 个技能组成连招,因此对于任意的 $$$1\leq i\leq n$$$ 要满足 $$$1\leq a_i\leq m$$$ (不必每个技能都用上), $$$m$$$ 由输入给出。

- 同一个技能不能释放太多次,因为那样会导致评分降低,若用 $$$cnt_i$$$ 表示连招中技能 $$$i$$$ 出现的次数,则对于任意的 $$$1\leq i\leq m$$$ ,要满足 $$$cnt_i\leq lim_i$$$ ,其中 $$$lim_i$$$ 由输入给出。

- 有些技能有释放限制,例如:只能在空中释放,因此在连招的某些特定位置不能释放某个技能,具体而言,有若干形如 $$$ a_{p_i}\neq s_i $$$ 的限制,$$$p_i$$$ 和 $$$s_i$$$ 由输入给出。

现在 YahAHa 想知道,有多少长度为 $$$n$$$ 的合法连招?由于他还想去打游戏,所以他让你帮他解决这个问题。由于答案可能会很大,YahAHa 只想知道答案对 $$$998244353$$$ 取模的结果。

Input

​第一行包括两个整数 $$$n,m$$$( $$$1\leq n\leq 20,1\leq m\leq 100$$$ )

​接下来一行,包括 $$$m$$$ 个整数,其中第 $$$i$$$ 个数表示 $$$lim_i$$$ ,表示第二条限制 ( $$$0\leq lim_i\leq n$$$ )。

​接下来一行包括一个整数 $$$r$$$ ( $$$0\leq r\leq 1000$$$ )

​接下来 $$$r$$$ 行,每行两个正整数 $$$p_i,s_i$$$ ,表示第三条限制,$$$1\leq p_i\leq n,1\leq s_i\leq m$$$ 。

Output

​仅一个整数,表示答案对 $$$998244353$$$ 取模的值

ExamplesInput
1 1
1
0
Output
1
Input
2 3
2 2 1
2
2 1
2 2
Output
2
Input
3 4
1 3 2 2
3
3 3
3 4
1 1
Output
21

加入题单

上一题 下一题 算法标签: