Many Optimization Problems

AtCoder

IDagc075_e

Time5000ms

Memory256MB

Difficulty—

> **Optimization Problem**You are given a length-$N$ sequence of non-negative integers $A=(A_1,A_2,\dots,A_N)$. Also, there is a length-$N+1$ sequence of non-negative integers $X=(0,0,\dots,0)$. > You will now perform the following operation for $i=1,2,\dots,N$: > > * Choose an integer $v$ satisfying $0 \le v \le A_i$, and add $v$ and $A_i-v$ to $X_i$ and $X_{i+1}$, respectively. > > Find the minimum possible value of the maximum value of $X$ at the end of the operations. You are given positive integers $N$, $M$, and a prime number $P$. Find the sum, modulo $P$, of the answers to the **Optimization Problem** for all sequences $A=(A_1,A_2,\dots,A_N)$ of non-negative integers with length $N$ and sum $M$. ## Constraints * $1 \le N \le 100$ * $1 \le M \le 10^{18}$ * $9 \times 10^8 \le P \le 10^9$ * $P$ is prime. ## Input The input is given from Standard Input in the following format: $N$ $M$ $P$ [samples]

Samples

Input #1

3 3 998244353

Output #1

13

For example, we solve the **Optimization Problem** for $A=(1,0,2)$. Here is a possible sequence of operations:

*   For $i = 1$, let $v = 1$. $X$ becomes $(1,0,0,0)$.
*   For $i = 2$, let $v = 0$. $X$ remains $(1,0,0,0)$.
*   For $i = 3$, let $v = 1$. $X$ becomes $(1,0,1,1)$.

Since the maximum value of $X$ cannot be made $0$ or less, the answer is $1$.
There are six other sequences with answer $1$ and three sequences with answer $2$, so the sum is $13$.

Input #2

10 135 998244353

Output #2

679877945

Input #3

100 1000000000000000000 924844033

Output #3

789282612

API Response (JSON)

{
  "problem": {
    "name": "Many Optimization Problems",
    "description": {
      "content": "> **Optimization Problem**You are given a length-$N$ sequence of non-negative integers $A=(A_1,A_2,\\dots,A_N)$. Also, there is a length-$N+1$ sequence of non-negative integers $X=(0,0,\\dots,0)$. > You",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc075_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "> **Optimization Problem**You are given a length-$N$ sequence of non-negative integers $A=(A_1,A_2,\\dots,A_N)$. Also, there is a length-$N+1$ sequence of non-negative integers $X=(0,0,\\dots,0)$.\n> You...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments