第 025 场 AtCoder Beginner Contest
翻译中…
Problem Statement
翻译中…
高橋君は縦 $5$ マス、横 $5$ マスの盤面に $1$ から $25$ までの整数を $1$ つずつ書き込もうとしています。
翻译中…
高橋君は以下の条件をすべて満たすように整数を配置しようと考えています。
翻译中…
- 整数は各マスに
$1$つずつ割り当てる。 - 縦または横に連続する
$3$つの整数をどのように取り出しても、それらは昇順または降順になっていない。すなわち、上から$i (1 ≦ i ≦ 5)$番目、左から$j (1 ≦ j ≦ 5)$番目のマスに書かれた整数を$n_{i,j}$としたとき、以下の$2$条件が成立する。
翻译中…
すでにいくつかのマスについては、どの整数を書き込むかは決まっています。あなたの課題は、上記の条件を満たすような残りの整数の配置の総数を計算することです。
翻译中…
Input
翻译中…
入力は以下の形式で標準入力から与えられる。
翻译中…
x_{1,1} x_{1,2} x_{1,3} x_{1,4} x_{1,5}
x_{2,1} x_{2,2} x_{2,3} x_{2,4} x_{2,5}
x_{3,1} x_{3,2} x_{3,3} x_{3,4} x_{3,5}
x_{4,1} x_{4,2} x_{4,3} x_{4,4} x_{4,5}
x_{5,1} x_{5,2} x_{5,3} x_{5,4} x_{5,5}翻译中…
$1$行目には、$5$つの整数$x_{1,1} (0 ≦ x_{1,1} ≦ 25)$と$x_{1,2} (0 ≦ x_{1,2} ≦ 25)$と$x_{1,3} (0 ≦ x_{1,3} ≦ 25)$と$x_{1,4} (0 ≦ x_{1,4} ≦ 25)$と$x_{1,5} (0 ≦ x_{1,5} ≦ 25)$が空白区切りで書かれている。$2$行目には、$5$つの整数$x_{2,1} (0 ≦ x_{2,1} ≦ 25)$と$x_{2,2} (0 ≦ x_{2,2} ≦ 25)$と$x_{2,3} (0 ≦ x_{2,3} ≦ 25)$と$x_{2,4} (0 ≦ x_{2,4} ≦ 25)$と$x_{2,5} (0 ≦ x_{2,5} ≦ 25)$が空白区切りで書かれている。$3$行目には、$5$つの整数$x_{3,1} (0 ≦ x_{3,1} ≦ 25)$と$x_{3,2} (0 ≦ x_{3,2} ≦ 25)$と$x_{3,3} (0 ≦ x_{3,3} ≦ 25)$と$x_{3,4} (0 ≦ x_{3,4} ≦ 25)$と$x_{3,5} (0 ≦ x_{3,5} ≦ 25)$が空白区切りで書かれている。$4$行目には、$5$つの整数$x_{4,1} (0 ≦ x_{4,1} ≦ 25)$と$x_{4,2} (0 ≦ x_{4,2} ≦ 25)$と$x_{4,3} (0 ≦ x_{4,3} ≦ 25)$と$x_{4,4} (0 ≦ x_{4,4} ≦ 25)$と$x_{4,5} (0 ≦ x_{4,5} ≦ 25)$が空白区切りで書かれている。$5$行目には、$5$つの整数$x_{5,1} (0 ≦ x_{5,1} ≦ 25)$と$x_{5,2} (0 ≦ x_{5,2} ≦ 25)$と$x_{5,3} (0 ≦ x_{5,3} ≦ 25)$と$x_{5,4} (0 ≦ x_{5,4} ≦ 25)$と$x_{5,5} (0 ≦ x_{5,5} ≦ 25)$が空白区切りで書かれている。
翻译中…
25
翻译中…
- 整数
$x_{i,j} (1 ≦ i ≦ 5, 1 ≦ j ≦ 5)$は上から$i$番目、左から$j$番目のマスに書かれる整数に関する情報である。$x_{i,j} = 0$ならそのマスに書かれる整数が決まっていないことを、$x_{i,j} ≠ 0$ならそのマスに書かれる整数が$x_{i,j}$であることを表す。
翻译中…
$1$以上$5$以下の$4$つの整数組$i,j,k,l$に関して、$x_{i,j} ≧ 1$かつ$x_{k,l} ≧ 1$かつ$(i,j) ≠ (k,l)$ならば、$x_{i,j} ≠ x_{k,l}$。$x_{i,j} ≠ 0$を満たす整数組$(i,j) (1 ≦ i ≦ 5, 1 ≦ j ≦ 5)$は$5$個以上存在する。
翻译中…
部分点
翻译中…
この問題には部分点が設定されている。
翻译中…
- データセット
$1$において、すべての入力には、$x_{i,j} ≠ 0$を満たす整数組$(i,j) (1 ≦ i ≦ 5, 1 ≦ j ≦ 5)$が$17$個以上存在する。データセット$1$に正解した場合は、$30$点が与えられる。 - 追加制約のないデータセット
$2$に正解した場合は、上記とは別に$70$点が与えられる。
翻译中…
Output
翻译中…
条件を満たすような残りの整数の配置の総数を $1000000007 (= 1,000,000,007)$ で割った余りを $1$ 行に出力せよ。出力の末尾に改行を入れること。
翻译中…
样例
Input #1
0 0 15 2 7
0 0 16 1 22
20 25 4 19 0
3 23 9 18 10
17 0 5 21 8
Output #1
2
- まだ書かれていない整数は $6, 11, 12, 13, 14, 24$ の $6$ つです。以下の $2$ 通りが、条件を満たす配置です。
| 14121527 131116122 20254196 32391810 17245218 | 14 | 12 | 15 | 2 | 7 | 13 | 11 | 16 | 1 | 22 | 20 | 25 | 4 | 19 | 6 | 3 | 23 | 9 | 18 | 10 | 17 | 24 | 5 | 21 | 8 | 14131527 121116122 20254196 32391810 17245218 | 14 | 13 | 15 | 2 | 7 | 12 | 11 | 16 | 1 | 22 | 20 | 25 | 4 | 19 | 6 | 3 | 23 | 9 | 18 | 10 | 17 | 24 | 5 | 21 | 8 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 14 | 12 | 15 | 2 | 7 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| 13 | 11 | 16 | 1 | 22 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| 20 | 25 | 4 | 19 | 6 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| 3 | 23 | 9 | 18 | 10 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| 17 | 24 | 5 | 21 | 8 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| 14 | 13 | 15 | 2 | 7 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| 12 | 11 | 16 | 1 | 22 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| 20 | 25 | 4 | 19 | 6 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| 3 | 23 | 9 | 18 | 10 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| 17 | 24 | 5 | 21 | 8 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
Input #2
10 14 13 15 11
16 0 17 0 18
0 19 0 20 9
21 12 22 0 23
0 24 0 25 0
Output #2
40320
- どのように残りを書いても条件を満たします。
Input #3
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
0 0 0 0 0
Output #3
0
- どのように置いても条件を満たさない場合があります。
Input #4
1 25 2 24 3
23 4 22 5 21
6 20 7 19 8
18 9 17 10 16
11 15 12 14 13
Output #4
1
- すでにすべての整数の配置が決まっている場合もあります。
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。