Tom and Jerry were sent to a kingdom for some intelligence purpose. They were ordered to draw a map of the kingdom.
It's known that the kingdom consists of nn cities, numbered from 11 to nn, along with n−1n−1 bidirectional roads connecting them. The cities form a binary tree, whose root is the kingdom's capital. The nodes on the tree either have no child, or a single left child, or a single right child, or both.
To avoid being caught spying, the commander ordered Tom and Jerry not to directly draw the map, but to record some specific information separately, which combined can deduce what the kingdom looks like.
When on a tree node, Tom was ordered to:
1. Record the label of current node.
2. Go to left child node(if any).
3. Go to right child node(if any).
Jerry was ordered to:
1. Go to left child node(if any).
2. Record the label of current node.
3. Go to right child node(if any).
But things often go south in Tom and Jerry's lives. When returned homeland with their information, they found that some of the numbers they wrote down are spotted. In despair, they decide to calculate how many kinds of form can the kingdom be according to the remaining information. As the number is large, you are only required to print it mod 998244353998244353.
2969: Kingdom
| Time Limit | $3$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $1$ | 正确数量 | $1$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
Description
Input
The first line contains an integer T(1≤T≤10)T(1≤T≤10), the number of test cases. Then TT cases follow.
For each test case:
In the first line, a integer n(1≤n≤100)n(1≤n≤100), the number of cities in the kingdom.
In the second line, nn integers a1,a2,a3,...,ana1,a2,a3,...,an separated by space, Tom's sequence.
In the third line, nn integers b1,b2,b3,...,bnb1,b2,b3,...,bn separated by space, Jerry's sequence(0≤ai,bi≤n0≤ai,bi≤n).
The spotted numbers are indicated by 00.
For each test case:
In the first line, a integer n(1≤n≤100)n(1≤n≤100), the number of cities in the kingdom.
In the second line, nn integers a1,a2,a3,...,ana1,a2,a3,...,an separated by space, Tom's sequence.
In the third line, nn integers b1,b2,b3,...,bnb1,b2,b3,...,bn separated by space, Jerry's sequence(0≤ai,bi≤n0≤ai,bi≤n).
The spotted numbers are indicated by 00.
Output
For each test case, output one line containing one integer, the number of corresponding kingdom's form mod 998244353998244353.
Sample Input复制
1
3
1 0 0
0 0 1
Sample Output复制
4
提示
Here are the 4 possible forms.
推荐代码 查看2969 所有题解 上传题解视频得图灵币
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$682 $ms] | 刘成健 | 461298 | 2019-09-06 17:09:54 |
| 内存最少[$11064 $KB] | 刘成健 | 461298 | 2019-09-06 17:09:54 |
| 第一AC | 刘成健 | 461298 | 2019-09-06 17:09:54 |
| 第一挑战 | 刘成健 | 461298 | 2019-09-06 17:09:54 |
赛题来源/所属竞赛 2019 Multi-University Training Contest 1 N/A
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|