/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 650 点
問題文
16 個の非負整数 X_{i, j, k, l} (i, j, k, l \in \lbrace 0, 1 \rbrace) が (i, j, k, l) の昇順に与えられます。
また、N = \displaystyle \sum_{i=0}^1 \sum_{j=0}^1 \sum_{k=0}^1 \sum_{l=0}^1 X_{i,j,k,l} とします。
0 または 1 からなる長さ N + 3 の数列 (A_1, A_2, ..., A_{N+3}) のうち、次の条件を満たすものの個数を 998244353 で割った余りを求めてください。
- 整数の 4 つ組 (i, j, k, l) (i, j, k, l \in \lbrace 0, 1 \rbrace) 全てについて、次の条件を満たす 1 以上 N 以下の整数 s はちょうど X_{i,j,k,l} 個存在する。
- A_s = i, A_{s + 1} = j, A_{s + 2} = k, A_{s + 3} = l である。
制約
- X_{i, j, k, l} は全て非負整数
- 1 \leq \displaystyle \sum_{i=0}^1 \sum_{j=0}^1 \sum_{k=0}^1 \sum_{l=0}^1 X_{i,j,k,l} \leq 10^6
入力
入力は以下の形式で標準入力から与えられる。
X_{0,0,0,0} X_{0,0,0,1} X_{0,0,1,0} X_{0,0,1,1} X_{0,1,0,0} X_{0,1,0,1} X_{0,1,1,0} X_{0,1,1,1} X_{1,0,0,0} X_{1,0,0,1} X_{1,0,1,0} X_{1,0,1,1} X_{1,1,0,0} X_{1,1,0,1} X_{1,1,1,0} X_{1,1,1,1}
出力
問題文の条件を満たす数列の個数を 998244353 で割った余りを出力せよ。
入力例 1
0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0
出力例 1
1
この入力は、 X_{1, 0, 1, 0} と X_{1, 1, 0, 1} が 1 でそれ以外は 0 であるような入力です。
このとき、条件を満たす数列は (1, 1, 0, 1, 0) の 1 通りのみです。
入力例 2
1 1 2 0 1 2 1 1 1 1 1 2 1 0 1 0
出力例 2
16
入力例 3
21 3 3 0 3 0 0 0 4 0 0 0 0 0 0 0
出力例 3
2024
入力例 4
62 67 59 58 58 69 57 66 67 50 68 65 59 64 67 61
出力例 4
741536606
Score: 650 points
Problem Statement
You are given 16 non-negative integers X_{i, j, k, l} (i, j, k, l \in \lbrace 0, 1 \rbrace) in ascending order of (i, j, k, l).
Let N = \displaystyle \sum_{i=0}^1 \sum_{j=0}^1 \sum_{k=0}^1 \sum_{l=0}^1 X_{i,j,k,l}.
Find the number, modulo 998244353, of sequences (A_1, A_2, ..., A_{N+3}) of length N + 3 consisting of 0s and 1s that satisfy the following condition.
- For every quadruple of integers (i, j, k, l) (i, j, k, l \in \lbrace 0, 1 \rbrace), there are exactly X_{i,j,k,l} integers s between 1 and N, inclusive, that satisfy:
- A_s = i, A_{s + 1} = j, A_{s + 2} = k, and A_{s + 3} = l.
Constraints
- X_{i, j, k, l} are all non-negative integers.
- 1 \leq \displaystyle \sum_{i=0}^1 \sum_{j=0}^1 \sum_{k=0}^1 \sum_{l=0}^1 X_{i,j,k,l} \leq 10^6
Input
The input is given from Standard Input in the following format:
X_{0,0,0,0} X_{0,0,0,1} X_{0,0,1,0} X_{0,0,1,1} X_{0,1,0,0} X_{0,1,0,1} X_{0,1,1,0} X_{0,1,1,1} X_{1,0,0,0} X_{1,0,0,1} X_{1,0,1,0} X_{1,0,1,1} X_{1,1,0,0} X_{1,1,0,1} X_{1,1,1,0} X_{1,1,1,1}
Output
Print the number, modulo 998244353, of sequences that satisfy the condition in the problem statement.
Sample Input 1
0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0
Sample Output 1
1
This input corresponds to the case where X_{1, 0, 1, 0} and X_{1, 1, 0, 1} are 1 and all others are 0.
In this case, only one sequence satisfies the condition, which is (1, 1, 0, 1, 0).
Sample Input 2
1 1 2 0 1 2 1 1 1 1 1 2 1 0 1 0
Sample Output 2
16
Sample Input 3
21 3 3 0 3 0 0 0 4 0 0 0 0 0 0 0
Sample Output 3
2024
Sample Input 4
62 67 59 58 58 69 57 66 67 50 68 65 59 64 67 61
Sample Output 4
741536606