G - Row Column Sums 2
Editorial
/ 
/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
非負整数を要素とする N 次正方行列であって、下記の 2 つの条件をともに満たすものの個数を 998244353 で割ったあまりを出力してください。
- すべての i = 1, 2, \ldots, N について、i 行目の要素の和は R_i である。
- すべての i = 1, 2, \ldots, N について、i 列目の要素の和は C_i である。
入力で与えられる R_i および C_i は 0 以上 2 以下の整数であることに注意してください（制約参照）。
制約
- 1 \leq N \leq 5000
- 0 \leq R_i \leq 2
- 0 \leq C_i \leq 2
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N R_1 R_2 \ldots R_N C_1 C_2 \ldots C_N
出力
答えを出力せよ。
入力例 1
3 1 1 1 0 1 2
出力例 1
3
条件を満たす行列は下記の 3 つです。
0 1 0 0 0 1 0 0 1
0 0 1 0 1 0 0 0 1
0 0 1 0 0 1 0 1 0
入力例 2
3 1 1 1 2 2 2
出力例 2
0
入力例 3
18 2 0 1 2 0 1 1 2 1 1 2 0 1 2 2 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 2 1 1 0 2 2
出力例 3
968235177
998244353 で割ったあまりを出力することに注意してください。
Score : 600 points
Problem Statement
Find the number, modulo 998244353, of square matrices of size N whose elements are non-negative integers, that satisfy both of the following two conditions:
- for all i = 1, 2, \ldots, N, the sum of the elements in the i-th row is R_i;
- for all i = 1, 2, \ldots, N, the sum of the elements in the i-th column is C_i.
Note that R_i and C_i given in the input are integers between 0 and 2 (see Constraints).
Constraints
- 1 \leq N \leq 5000
- 0 \leq R_i \leq 2
- 0 \leq C_i \leq 2
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N R_1 R_2 \ldots R_N C_1 C_2 \ldots C_N
Output
Print the answer.
Sample Input 1
3 1 1 1 0 1 2
Sample Output 1
3
The following 3 matrices satisfy the conditions:
0 1 0 0 0 1 0 0 1
0 0 1 0 1 0 0 0 1
0 0 1 0 0 1 0 1 0
Sample Input 2
3 1 1 1 2 2 2
Sample Output 2
0
Sample Input 3
18 2 0 1 2 0 1 1 2 1 1 2 0 1 2 2 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 2 1 1 0 2 2
Sample Output 3
968235177
Be sure to print the count modulo 998244353.