#P17852. [Ontak2019]MAL
[Ontak2019]MAL
— 两笔作画
有一块 的白色画布,划分成单位方格。行从上到下、列从左到右编号。
画家只画两笔。第一笔从 出发到 ,每次向右或向下移动一格。第二笔从 回到 ,每次向左或向上移动一格。两笔经过的所有格子都会变黑,经过两次仍只算一个黑格,起点和终点也会被涂黑。
给定每一列应有的黑格数 以及每一行应有的黑格数 ,判断能否按要求完成画作,并计算画法数量,对 取模。
两种画法不同,当且仅当存在一个格子,在某一笔中被一种画法经过、而另一种画法的同一笔没有经过。因此两笔有区别,只有最终黑格集合相同并不一定是同一种画法。
输入格式
第一行一个整数 。
第二行 个整数 ,表示各列黑格数。
第三行 个整数 ,表示各行黑格数。
输出格式
第一行:可行时输出 YES,否则输出 NO。
第二行输出画法数量对 取模的结果,不可行时输出 0。
原站对仅正确判断可行性的程序给予该测试30%的分数,但仍要求输出第二行。本题标程输出完整答案。
数据范围
,。
| 子任务 | 上限 | 分值 |
|---|---|---|
| 1 | 20 | 10 |
| 2 | 100 | |
| 3 | 1000 | 20 |
| 4 | 10000 | |
| 5 | 100000 | |
| 6 | 1000000 |
英文叙述中有一处将 对调;这里与原题输入格式及波兰文一致:先列数 ,后行数 。
样例 1
输入:
3
2 2 1
1 2 2
输出:
YES
1
样例 2
输入:
3
3 3 3
1 1 2
输出:
NO
0