← 返回题目列表

AtCoder · abc025_d

D. 25 个整数

中文机器翻译题面 查看原题

問題文

高桥君是垂直的 5 方形,水平 5 方板上 直到 1 从 25 的整数 1 我正在尝试一一写。

高桥正在考虑排列整数,使它们满足以下所有条件。

  • 每个方格中的整数 按 1 分配。
  • 垂直或水平连续 3 无论您如何取整数,它们都不是按升序或降序排列的。即从上面 左起第 i (1 ≦ i ≦ 5) 第 j (1 ≦ j ≦ 5) 个方格中写入的整数是 n_{i,j} ,以下 2 满足条件。
    • n_{i,j} < n_{i+1,j} < n_{i+2,j} 或 满足 n_{i,j} > n_{i+1,j} > n_{i+2,j} 的一组整数 (i,j) (1 ≦ i ≦ 3, 1 ≦ j ≦ 5) 不存在。
    • n_{i,j} < n_{i,j+1} < n_{i,j+2} 或 满足 n_{i,j} > n_{i,j+1} > n_{i,j+2} 的一组整数 (i,j) (1 ≦ i ≦ 5, 1 ≦ j ≦ 3) 不存在。

我们已经决定了哪些整数将被写入一些方格中。你的任务是计算满足上述条件的剩余整数排列的总数。 在


入力

输入是按以下格式从标准输入给出的。

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 点。

出力

计算满足条件的剩余整数排列总数。 除以 1000000007 (= 1,000,000,007) 后的余数 在 1 行输出。在输出末尾插入换行符。


入力例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

出力例1

2
  • 尚未写入的整数是 6, 11, 12, 13, 14, 24 的 6 一。下面 2 街道是满足条件的布置。
14121527
131116122
20254196
32391810
17245218
14131527
121116122
20254196
32391810
17245218

入力例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

出力例2

40320
  • 不管剩下的怎么写,它都会满足条件。

入力例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

出力例3

0
  • 无论怎么放置,都可能无法满足条件。

入力例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

出力例4

1
  • 在某些情况下,所有整数的位置已经确定。 给出了