{"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_y\\gets a_y-1$。同时在与点 $y$ 相邻的两个点中**等概率选择**一个，其点权将被 $+1$。\n\n你希望期望的修改次数最少，所以求在最优策略下的期望操作次数（操作 1 不计入）。\n\n## Input\n\n第一行一个整数 $n$。\\\n第二行 $n$ 个整数表示 $a_{1\\dots n}$。\n\n## Output\n\n一个整数，表示答案。输出时答案对 $1004535809$ 取模。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/peaku0fe.png)\n\n## Note\n\n### 样例 $1$ 解释\n\n选定 $x=2$，进行 $114514$ 次操作，每次的 $y=1$。\n\n### 数据规模\n\n**本题采用捆绑测试。**\n\n| $\\text{Subtask}$ | $n\\le$ |分值 |\n| :----------: | :----------: |:----------: |\n| $1$ | $2$ | $5$ |\n| $2$ | $10^3$ | $20$ |\n| $3$ | $10^4$ | $20$ |\n| $4$ | $10^5$ | $20$ |\n| $5$ | $10^6$ | $35$ |\n\n对于 $100\\%$ 的数据，$2\\le n\\le 10^6$，$0\\le a_i<1004535809$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8850","tags":["数学","递推","2022","洛谷原创","洛谷月赛"],"sample_group":[["2\n114514 1919810","114514"],["3\n1 1 2","4"]],"created_at":"2026-03-03 11:09:25"}}