题目详情题解（0）讨论（0）提交记录（0）

AT_abc025_d.[ABC025D] 25個の整数

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥君打算在一个 55 行 55 列的棋盘上，将 11 到 2525 的整数各写一次。

高桥君希望整数的摆放满足以下所有条件：

  • 每个格子分配一个整数。
  • 无论在纵向或横向连续取出 33 个整数，这 33 个数都不会严格递增或严格递减。即，设从上到下第 ii 行，从左到右第 jj 列的格子中写的整数为 ni,jn_{i,j}，则需满足以下两个条件：
    • 不存在整数组 (i,j) (1≤i≤3, 1≤j≤5)(i,j)\ (1\leq i\leq 3,\ 1\leq j\leq 5)，使得 ni,j<ni+1,j<ni+2,jn_{i,j}<n_{i+1,j}<n_{i+2,j} 或 ni,j>ni+1,j>ni+2,jn_{i,j}>n_{i+1,j}>n_{i+2,j}。
    • 不存在整数组 (i,j) (1≤i≤5, 1≤j≤3)(i,j)\ (1\leq i\leq 5,\ 1\leq j\leq 3)，使得 ni,j<ni,j+1<ni,j+2n_{i,j}<n_{i,j+1}<n_{i,j+2} 或 ni,j>ni,j+1>ni,j+2n_{i,j}>n_{i,j+1}>n_{i,j+2}。

部分格子的整数已经确定。你的任务是计算，满足上述条件的剩余整数的所有可能摆放方案数。

输入格式

输入为如下形式，从标准输入读入。

x1,1x_{1,1} x1,2x_{1,2} x1,3x_{1,3} x1,4x_{1,4} x1,5x_{1,5}
x2,1x_{2,1} x2,2x_{2,2} x2,3x_{2,3} x2,4x_{2,4} x2,5x_{2,5}
x3,1x_{3,1} x3,2x_{3,2} x3,3x_{3,3} x3,4x_{3,4} x3,5x_{3,5}
x4,1x_{4,1} x4,2x_{4,2} x4,3x_{4,3} x4,4x_{4,4} x4,5x_{4,5}
x5,1x_{5,1} x5,2x_{5,2} x5,3x_{5,3} x5,4x_{5,4} x5,5x_{5,5}

  • 第 11 行包含 55 个整数 x1,1 (0≤x1,1≤25)x_{1,1}\ (0\leq x_{1,1}\leq 25)、x1,2 (0≤x1,2≤25)x_{1,2}\ (0\leq x_{1,2}\leq 25)、x1,3 (0≤x1,3≤25)x_{1,3}\ (0\leq x_{1,3}\leq 25)、x1,4 (0≤x1,4≤25)x_{1,4}\ (0\leq x_{1,4}\leq 25)、x1,5 (0≤x1,5≤25)x_{1,5}\ (0\leq x_{1,5}\leq 25)，以空格分隔。
  • 第 22 行包含 55 个整数 x2,1 (0≤x2,1≤25)x_{2,1}\ (0\leq x_{2,1}\leq 25)、x2,2 (0≤x2,2≤25)x_{2,2}\ (0\leq x_{2,2}\leq 25)、x2,3 (0≤x2,3≤25)x_{2,3}\ (0\leq x_{2,3}\leq 25)、x2,4 (0≤x2,4≤25)x_{2,4}\ (0\leq x_{2,4}\leq 25)、x2,5 (0≤x2,5≤25)x_{2,5}\ (0\leq x_{2,5}\leq 25)，以空格分隔。
  • 第 33 行包含 55 个整数 x3,1 (0≤x3,1≤25)x_{3,1}\ (0\leq x_{3,1}\leq 25)、x3,2 (0≤x3,2≤25)x_{3,2}\ (0\leq x_{3,2}\leq 25)、x3,3 (0≤x3,3≤25)x_{3,3}\ (0\leq x_{3,3}\leq 25)、x3,4 (0≤x3,4≤25)x_{3,4}\ (0\leq x_{3,4}\leq 25)、x3,5 (0≤x3,5≤25)x_{3,5}\ (0\leq x_{3,5}\leq 25)，以空格分隔。
  • 第 44 行包含 55 个整数 x4,1 (0≤x4,1≤25)x_{4,1}\ (0\leq x_{4,1}\leq 25)、x4,2 (0≤x4,2≤25)x_{4,2}\ (0\leq x_{4,2}\leq 25)、x4,3 (0≤x4,3≤25)x_{4,3}\ (0\leq x_{4,3}\leq 25)、x4,4 (0≤x4,4≤25)x_{4,4}\ (0\leq x_{4,4}\leq 25)、x4,5 (0≤x4,5≤25)x_{4,5}\ (0\leq x_{4,5}\leq 25)，以空格分隔。
  • 第 55 行包含 55 个整数 x5,1 (0≤x5,1≤25)x_{5,1}\ (0\leq x_{5,1}\leq 25)、x5,2 (0≤x5,2≤25)x_{5,2}\ (0\leq x_{5,2}\leq 25)、x5,3 (0≤x5,3≤25)x_{5,3}\ (0\leq x_{5,3}\leq 25)、x5,4 (0≤x5,4≤25)x_{5,4}\ (0\leq x_{5,4}\leq 25)、x5,5 (0≤x5,5≤25)x_{5,5}\ (0\leq x_{5,5}\leq 25)，以空格分隔。

上述 2525 个整数表示如下信息：

  • 整数 xi,j (1≤i≤5, 1≤j≤5)x_{i,j}\ (1\leq i\leq 5,\ 1\leq j\leq 5) 表示从上到下第 ii 行，从左到右第 jj 列的格子中写的整数。若 xi,j=0x_{i,j}=0，表示该格子的整数未确定；若 xi,j≠0x_{i,j}\neq 0，则该格子的整数为 xi,jx_{i,j}。

此外，输入保证以下条件：

  • 对于 1≤i,k≤5, 1≤j,l≤51\leq i,k\leq 5,\ 1\leq j,l\leq 5，若 xi,j≥1x_{i,j}\geq 1 且 xk,l≥1x_{k,l}\geq 1 且 (i,j)≠(k,l)(i,j)\neq (k,l)，则 xi,j≠xk,lx_{i,j}\neq x_{k,l}。
  • 满足 xi,j≠0x_{i,j}\neq 0 的格子 (i,j)(i,j) 至少有 55 个。

输出格式

输出满足条件的剩余整数的所有可能摆放方案数，对 1000000007 (=1,000,000,007)1000000007\ (=1,000,000,007) 取模。输出末尾需换行。

输入输出样例

  • 输入#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

  • 输入#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

说明/提示

部分分

本题设有部分分。

  • 数据集 11：所有输入中，满足 xi,j≠0x_{i,j}\neq 0 的格子 (i,j)(i,j) 至少有 1717 个。通过数据集 11 可得 3030 分。
  • 数据集 22：无额外限制，通过数据集 22 可得 7070 分。

样例说明 1

  • 还未填写的整数为 6, 11, 12, 13, 14, 246,\ 11,\ 12,\ 13,\ 14,\ 24 共 66 个。以下 22 种方案满足条件。
    14121527131116122202541963239181017245218
    14131527121116122202541963239181017245218

样例说明 2

  • 无论如何填写剩余的数都能满足条件。

样例说明 3

  • 有时无论如何填写都无法满足条件。

样例说明 4

  • 若所有整数的位置都已确定，也需输出方案数。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页