Increment Decrement

AtCoder

IDagc049_e

Time2000ms

Memory256MB

Difficulty—

Maroon came up with the following problem: * * * Snuke has an integer sequence $a$ of length $N$. Initially, $a_i=0$ for every $i$ ($1 \leq i \leq N$). Snuke will repeat the following two operations any number of times in any order: * Operation $1$: Replace $a_i$ with $a_i+x$, where $i$ ($1 \leq i \leq N$) and $x$ ($x=1$ or $x=-1$) are integers of his choice. The cost of doing this operation once is $1$. * Operation $2$: Replace $a_i$ with $a_i+x$ for every $i$ ($l \leq i \leq r$), where $l$, $r$ ($1 \leq l \leq r \leq N$) and $x$ ($x=1$ or $x=-1$) are integers of his choice. The cost of doing this operation once is $C$. You are given an integer sequence $A$ of length $N$. Snuke wants to make $a_i=A_i$ for every $i$. Find the minimum total cost needed to achieve his objective. * * * However, during the preparation of this problem, too many unexpected solutions were found, so Maroon changed the problem into the following: * * * Snuke has $N$ integer sequences $B_1,B_2,\cdots,B_N$ and integers $C$ and $K$. The length of every sequence $B_i$ ($1 \leq i \leq N$) is $K$. Now, he wants to make an integer sequence $A$ of length $N$ and find the answer to the problem above. The value of $A_i$ will be chosen from $B_{i,1},B_{i,2},\cdots,B_{i,K}$. Here, even if there are duplicated values in $B_{i,1},B_{i,2},\cdots,B_{i,K}$, we still distinguish those values. That is, there are $K^N$ ways to make $A$. Find the sum of the answers to the problem above over all the ways to make $A$, modulo $(10^9+7)$. * * * Solve this problem. ## Constraints * $1 \leq N \leq 50$ * $1 \leq C \leq N$ * $1 \leq K \leq 50$ * $1 \leq B_{i,j} \leq 10^9$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $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}$ [samples]

Samples

Input #1

Output #1

6

We have $A=(2,3,1,2,1)$. Below is one optimal sequence of operations:

*   Let $l=1,r=5,x=1$ and do Operation $2$, resulting in $a=(1,1,1,1,1)$.
*   Let $l=1,r=4,x=1$ and do Operation $2$, resulting in $a=(2,2,2,2,1)$.
*   Let $i=2,x=1$ and do Operation $1$, resulting in $a=(2,3,2,2,1)$.
*   Let $i=3,x=-1$ and do Operation $1$, resulting in $a=(2,3,1,2,1)$.

Input #2

Output #2

Input #3

Output #3

Input #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

Output #4

877826779

API Response (JSON)

{
  "problem": {
    "name": "Increment Decrement",
    "description": {
      "content": "Maroon came up with the following problem: * * * Snuke has an integer sequence $a$ of length $N$. Initially, $a_i=0$ for every $i$ ($1 \\leq i \\leq N$). Snuke will repeat the following two operations",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc049_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Maroon came up with the following problem:\n\n* * *\n\nSnuke has an integer sequence $a$ of length $N$. Initially, $a_i=0$ for every $i$ ($1 \\leq i \\leq N$).\nSnuke will repeat the following two operations...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments