AT_agc049_e.[AGC049E] Increment Decrement

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

maroon くん想出了如下的问题。

すぬけ君有一个长度为 $N$ 的整数序列 $a$ 。最开始，对于所有 $i$ （ $1 \leq i \leq N$ ），都有 $a_i=0$ 。

すぬけ君可以按任意顺序、任意次数重复以下两种操作：

操作 $1$ ：选择任意整数 $i$ （ $1 \leq i \leq N$ ）和 $x$ （ $x=1$ 或 $x=-1$ ），将 $a_i$ 替换为 $a_i+x$ 。每执行一次该操作，花费 $1$ 的代价。
操作 $2$ ：选择任意整数 $l,r$ （ $1 \leq l \leq r \leq N$ ）和 $x$ （ $x=1$ 或 $x=-1$ ），对于所有 $i$ （ $l \leq i \leq r$ ），将 $a_i$ 替换为 $a_i+x$ 。每执行一次该操作，花费 $C$ 的代价。

给定一个长度为 $N$ 的整数序列 $A$ 。すぬけ君的目标是使得对于所有 $i$ ，都有 $a_i=A_i$ 。请你求出达成目标所需的总代价的最小值。

然而，在准备这个问题时，发现了许多未曾预料的解法。因此，问题被修改如下：

现在，すぬけ君有 $N$ 个整数序列 $B_1,B_2,\cdots,B_N$ ，以及整数 $C,K$ 。每个 $B_i$ （ $1 \leq i \leq N$ ）都是长度为 $K$ 的整数序列。

接下来，すぬけ君要构造一个长度为 $N$ 的整数序列 $A$ ，并求出上述问题的答案。 $A_i$ 的取值可以从 $B_{i,1},B_{i,2},\cdots,B_{i,K}$ 中任选一个。即使 $B_i$ 中有重复的值，也要将它们视为不同的选择。也就是说， $A$ 的构造方式共有 $K^N$ 种。

请你计算，对于所有可能的 $A$ ，上述问题的答案之和，并对 $10^9+7$ 取模。

请解决本题。

输入格式

输入以如下格式从标准输入读入。

$N$ $C$ $K$ $B_{1,1}$ $B_{1,2}$ $\cdots$ $B_{1,K}$ $B_{2,1}$ $B_{2,2}$ $\cdots$ $B_{2,K}$ $\vdots$ $B_{N,1}$ $B_{N,2}$ $\cdots$ $B_{N,K}$

输出格式

请输出答案。

输入输出样例

输入#1
```
5 2 1
2
3
1
2
1
```
输出#1
```
6
```
输入#2
```
3 2 3
1 2 3
1 2 3
1 2 3
```
输出#2
```
126
```
输入#3
```
10 4 1
8
10
10
1
5
9
5
5
9
1
```
输出#3
```
45
```

输入#4

10 5 10
79 48 35 56 16 26 37 6 75 23
39 99 57 100 49 90 18 9 12 91
29 97 49 86 30 94 78 63 49 22
100 27 48 91 66 14 6 20 23 84
12 60 99 75 88 95 61 58 20 46
10 11 30 38 55 94 9 52 92 75
27 22 46 85 83 88 50 63 95 91
49 59 19 37 53 27 11 26 2 91
95 36 20 76 84 41 59 95 67 66
52 60 17 11 28 57 75 69 95 24

输出#4

877826779

说明/提示

数据范围

$1 \leq N \leq 50$
$1 \leq C \leq N$
$1 \leq K \leq 50$
$1 \leq B_{i,j} \leq 10^9$
所有输入均为整数。

样例解释 1

$A=(2,3,1,2,1)$ 。一种最优操作方案如下：

以 $l=1,r=5,x=1$ 执行操作 $2$ ，此时 $a=(1,1,1,1,1)$ 。
以 $l=1,r=4,x=1$ 执行操作 $2$ ，此时 $a=(2,2,2,2,1)$ 。
以 $i=2,x=1$ 执行操作 $1$ ，此时 $a=(2,3,2,2,1)$ 。
以 $i=3,x=-1$ 执行操作 $1$ ，此时 $a=(2,3,1,2,1)$ 。

由 ChatGPT 4.1 翻译

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

首页