/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
各成分が 0,1 である N 次正方行列 A,B について、以下の条件を満たしているとき A と B は 似ている と言います。
- 各行の総和が等しい。つまり、どの i=1,\dots,N についても A_{i,1} + \dots + A_{i,N} = B_{i,1} + \dots + B_{i,N}
- 各列の総和が等しい。つまり、どの j=1,\dots,N についても A_{1,j} + \dots + A_{N,j} = B_{1,j} + \dots + B_{N,j}
また、各成分が 0,1 である N 次正方行列 A と整数 i,j (1 \leq i,j \leq N) について、A と似ているどの行列 B についても A_{i,j} = B_{i,j} が成り立つとき、A の i 行 j 列成分は 固定されている と言います。
以下の Q 個のクエリに答えてください。
- i 番目のクエリ：各成分が 0,1 である N 次正方行列であって、固定されている成分がちょうど K_i 個であるようなものが存在するなら
Yes、そうでないならNoを出力せよ。
制約
- 2 \le N \le 30
- 1 \le Q \le N^2+1
- 0 \le K_i \le N^2
- K_i \ne K_j (1 \le i < j \le Q)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N Q K_1 K_2 \vdots K_Q
出力
Q 行に出力せよ。 i (1 \le i \le Q) 行目には i 番目のクエリの答えを出力せよ。
入力例 1
3 3 0 9 7
出力例 1
Yes Yes No
1 番目のクエリ： 例えば、以下のような行列 X は、固定されている成分が 0 個です。
1 0 0 0 1 0 0 0 1
なぜなら、次のように列を循環シフトさせていったものはすべて X と似ており、どの成分も 0 にも 1 にもなりうるためです。
0 0 1 1 0 0 0 1 0
0 1 0 0 0 1 1 0 0
2 番目のクエリ： 例えば、以下のような行列 X は、固定されている成分が 9 個です。
0 0 1 0 1 1 1 1 1
なぜなら、似ている行列は X 以外に存在せず、すべての成分が固定されているためです。
3 番目のクエリ： 固定されている成分がちょうど 7 個であるような行列は存在しません。
入力例 2
29 6 186 681 18 108 123 321
出力例 2
No Yes No Yes No Yes
Score : 900 points
Problem Statement
For two N \times N matrices A and B whose elements are 0 or 1, we say that A and B are similar if they satisfy the following conditions:
- The sums of corresponding rows are equal. That is, A_{i,1} + \dots + A_{i,N} = B_{i,1} + \dots + B_{i,N} for any i=1,\dots,N.
- The sums of corresponding columns are equal. That is, A_{1,j} + \dots + A_{N,j} = B_{1,j} + \dots + B_{N,j} for any j=1,\dots,N.
Furthermore, for an N \times N matrix A whose elements are 0 or 1, and integers i,j (1 \leq i,j \leq N), we say that the element at row i column j is fixed if A_{i,j} = B_{i,j} holds for any matrix B that is similar to A.
Answer the following Q queries:
- The i-th query: If there exists an N \times N matrix whose elements are 0 or 1 such that exactly K_i elements are fixed, output
Yes; otherwise, outputNo.
Constraints
- 2 \le N \le 30
- 1 \le Q \le N^2+1
- 0 \le K_i \le N^2
- K_i \ne K_j (1 \le i < j \le Q)
- All inputs are integers
Input
The input is given from Standard Input in the following format:
N Q K_1 K_2 \vdots K_Q
Output
Output Q lines. For the i-th line (1 \le i \le Q), output the answer for the i-th query.
Sample Input 1
3 3 0 9 7
Sample Output 1
Yes Yes No
Query 1: For example, the following matrix X has exactly 0 fixed elements.
1 0 0 0 1 0 0 0 1
This is because all the following matrices, obtained by cyclically shifting the columns, are similar to X, and each element can be either 0 or 1.
0 0 1 1 0 0 0 1 0
0 1 0 0 0 1 1 0 0
Query 2: For example, the following matrix X has exactly 9 fixed elements.
0 0 1 0 1 1 1 1 1
This is because no other matrix similar to X exists, and all elements are fixed.
Query 3: No matrix exists with exactly 7 fixed elements.
Sample Input 2
29 6 186 681 18 108 123 321
Sample Output 2
No Yes No Yes No Yes