[JRKSJ R5] Jalapeno and Garlic

Luogu
IDLGP8850
Time500ms
Memory128MB
DifficultyP5
数学递推2022洛谷原创洛谷月赛
一个 $n$ 个点的环,点有点权 $a$,编号依次从 $1\sim n$。点 $1$ 与点 $n$ 相邻。 你希望只存在一个 $x\in[1,n]$ 满足 $a_x\ne 0$。为此,你需要按下面流程进行操作: 1. 选定一个 $x$,表示最终使得 $a_x\ne 0$。**此后不能更改 $x$ 的选择。** 2. 进行若干次修改操作,每次操作你可以选定一个 $y\in[1,n]$,将 $a_y\gets a_y-1$。同时在与点 $y$ 相邻的两个点中**等概率选择**一个,其点权将被 $+1$。 你希望期望的修改次数最少,所以求在最优策略下的期望操作次数(操作 1 不计入)。 ## Input 第一行一个整数 $n$。\ 第二行 $n$ 个整数表示 $a_{1\dots n}$。 ## Output 一个整数,表示答案。输出时答案对 $1004535809$ 取模。 [samples] ## Background ![](https://cdn.luogu.com.cn/upload/image_hosting/peaku0fe.png) ## Note ### 样例 $1$ 解释 选定 $x=2$,进行 $114514$ 次操作,每次的 $y=1$。 ### 数据规模 **本题采用捆绑测试。** | $\text{Subtask}$ | $n\le$ |分值 | | :----------: | :----------: |:----------: | | $1$ | $2$ | $5$ | | $2$ | $10^3$ | $20$ | | $3$ | $10^4$ | $20$ | | $4$ | $10^5$ | $20$ | | $5$ | $10^6$ | $35$ | 对于 $100\%$ 的数据,$2\le n\le 10^6$,$0\le a_i<1004535809$。
Samples
Input #1
2
114514 1919810
Output #1
114514
Input #2
3
1 1 2
Output #2
4
API Response (JSON)
{
  "problem": {
    "name": "[JRKSJ R5] Jalapeno and Garlic",
    "description": {
      "content": "一个 $n$ 个点的环,点有点权 $a$,编号依次从 $1\\sim n$。点 $1$ 与点 $n$ 相邻。 你希望只存在一个 $x\\in[1,n]$ 满足 $a_x\\ne 0$。为此,你需要按下面流程进行操作: 1. 选定一个 $x$,表示最终使得 $a_x\\ne 0$。**此后不能更改 $x$ 的选择。** 2. 进行若干次修改操作,每次操作你可以选定一个 $y\\in[1,n]$,将 $a_",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 500,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8850"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一个 $n$ 个点的环,点有点权 $a$,编号依次从 $1\\sim n$。点 $1$ 与点 $n$ 相邻。\n\n你希望只存在一个 $x\\in[1,n]$ 满足 $a_x\\ne 0$。为此,你需要按下面流程进行操作:\n\n1. 选定一个 $x$,表示最终使得 $a_x\\ne 0$。**此后不能更改 $x$ 的选择。**\n2. 进行若干次修改操作,每次操作你可以选定一个 $y\\in[1,n]$,将 $a_...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments