Hello, Solitude.

Luogu

IDLGP9684

Time2000ms

Memory512MB

DifficultyP7

动态规划 DP多项式洛谷原创O2优化洛谷月赛

有一张很长的桌子，桌子一边摆了 $n+2$ 张椅子，从左到右依次标号为 $0,1,\dots,n+1$，任意两张相邻的椅子的距离相同。初始 $0$ 号和 $n+1$ 号椅子上各坐着一个人。然后有 $m$ 个人依次按照如下的规则入座： - 先均匀随机选择一个空着的座位。 - 若移动到相邻的座位，能使其到相邻的人的最小距离增大，则移动到相邻座位。可以证明上述操作进行有限步后一定会停下。对于 $1\sim n$ 号的每一张椅子，求出其上面有人坐的概率。 ## Input 第一行输入两个整数 $n,m$。 ## Output 输出 $n$ 行，每行一个整数，第 $i$ 行的整数代表第 $i$ 张椅子上有人坐的概率对 $998\,244\,353$ 取模的结果。 [samples] ## Background @【数据删除】 : 我【数据删除】了。 || @【数据删除】 : 你投哪个 || @【数据删除】 : 雪乃对美琴（悲） ## Note #### 样例 1 解释下面是一种可能的落座方法： 0. 初始 $1\sim n$ 都没有人落座。 1. 选定 $x=2$，到最近的人（位于座位 $0$）距离为 $2$； 1. 向右移动到 $3$ 号椅子后，到最近的人的距离增大至 $3$，所以 $x\gets x+1$； 2. 再向右移动到 $4$ 的话，到最近的人（位于座位 $6$）的距离依旧为 $3$，所以在 $3$ 号椅子落座。 2. 选定 $x=6$，到最近的人（位于座位 $7$）距离为 $1$； 1. 向左移动到 $5$ 号椅子后，到最近的人的距离增大至 $2$，所以 $x\gets x-1$； 2. 再向左/右移动话，到最近的人的距离均会减小，所以在 $5$ 号椅子落座。 3. 选定 $x=4$，由于无法左右移动，所以直接在 $4$ 号椅子落座。最终，$3,4,5$ 号椅子上有人坐。 ### 数据规模与约定对于所有数据，$1\le n\le 5\times 10^5$，$0\le m\le n$。 ### 子任务 | # | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | | 0 | 样例 | 0 | | 1 | $n\le20$ | 9 | | 2 | $n\le100$ | 10 | | 3 | $n\le500$ | 12 | | 4 | $n\le2000$ | 11 | | 5 | $n\le5000$ | 12 | | 6 | $\exists k\in \mathbb{N}$ 使得 $n=2^k-1$ | 13 | | 7 | $n\le 10^5$ | 15 | | 8 | - | 18 |

Samples

Input #1

6 3

Output #1

API Response (JSON)

{
  "problem": {
    "name": "Hello, Solitude.",
    "description": {
      "content": "有一张很长的桌子，桌子一边摆了 $n+2$ 张椅子，从左到右依次标号为 $0,1,\\dots,n+1$，任意两张相邻的椅子的距离相同。 初始 $0$ 号和 $n+1$ 号椅子上各坐着一个人。然后有 $m$ 个人依次按照如下的规则入座： - 先均匀随机选择一个空着的座位。 - 若移动到相邻的座位，能使其到相邻的人的最小距离增大，则移动到相邻座位。可以证明上述操作进行有限步后一定会停下。 对于 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9684"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一张很长的桌子，桌子一边摆了 $n+2$ 张椅子，从左到右依次标号为 $0,1,\\dots,n+1$，任意两张相邻的椅子的距离相同。\n\n初始 $0$ 号和 $n+1$ 号椅子上各坐着一个人。然后有 $m$ 个人依次按照如下的规则入座：\n\n- 先均匀随机选择一个空着的座位。\n- 若移动到相邻的座位，能使其到相邻的人的最小距离增大，则移动到相邻座位。可以证明上述操作进行有限步后一定会停下。\n\n对于 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments