310577: CF1854C. Expected Destruction
Description
You have a set $S$ of $n$ distinct integers between $1$ and $m$.
Each second you do the following steps:
- Pick an element $x$ in $S$ uniformly at random.
- Remove $x$ from $S$.
- If $x+1 \leq m$ and $x+1$ is not in $S$, add $x+1$ to $S$.
What is the expected number of seconds until $S$ is empty?
Output the answer modulo $1\,000\,000\,007$.
Formally, let $P = 1\,000\,000\,007$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{a}{b}$, where $a$ and $b$ are integers and $b \not \equiv 0 \pmod{P}$. Output the integer equal to $a \cdot b^{-1} \bmod P$. In other words, output an integer $z$ such that $0 \le z < P$ and $z \cdot b \equiv a \pmod{P}$.
InputThe first line contains two integers $n$ and $m$ ($1 \leq n \leq m \leq 500$) — the number of elements in the set $S$ and the upper bound on the value of the elements in $S$.
The second line contains $n$ integers $S_1,\,S_2,\,\dots,\,S_n$ ($1 \leq S_1 < S_2 < \ldots < S_n \leq m$) — the elements of the set $S$.
OutputOutput a single integer — the expected number of seconds until $S$ is empty, modulo $1\,000\,000\,007$.
ExamplesInput2 3 1 3Output
750000009Input
5 10 1 2 3 4 5Output
300277731Input
5 10 2 3 6 8 9Output
695648216Input
1 100 1Output
100Note
For test 1, here is a list of all the possible scenarios and their probabilities:
- $[1, 3]$ (50% chance) $\to$ $[1]$ $\to$ $[2]$ $\to$ $[3]$ $\to$ $[]$
- $[1, 3]$ (50% chance) $\to$ $[2, 3]$ (50% chance) $\to$ $[2]$ $\to$ $[3]$ $\to$ $[]$
- $[1, 3]$ (50% chance) $\to$ $[2, 3]$ (50% chance) $\to$ $[3]$ $\to$ $[]$
Adding them up, we get $\frac{1}{2}\cdot 4 + \frac{1}{4} \cdot 4 + \frac{1}{4} \cdot 3 = \frac{15}{4}$. We see that $750000009 \cdot 4 \equiv 15 \pmod{1\,000\,000\,007}$.
Input
题意翻译
给定大小为 $n$ 的正整数集合 $S$,$S$ 中的每个数在 $1\sim m$ 之间。 每一秒进行如下操作: 1. 从 $S$ 中等概率随机选择一个数 $x$。 2. 将 $x$ 从 $S$ 中删去。 3. 若 $x + 1\leq m$ 且 $x + 1\notin S$,则将 $x + 1$ 加入 $S$。 求 $S$ 变成空集的期望时间,对 $10 ^ 9 + 7$ 取模。 $1\leq n\leq m \leq 500$,$1\leq S_1 < S_2 < \cdots < S_n \leq m$。Output
你有一个由n个不同的整数组成的集合S,这些整数介于1和m之间。每一秒钟你按照以下步骤操作:
1. 从S中均匀随机选择一个元素x。
2. 将x从S中移除。
3. 如果x+1≤m并且x+1不在S中,将x+1添加到S中。
问S变空所需的期望秒数是多少?
输出答案对1,000,000,007取模的结果。
输入数据格式:
第一行包含两个整数n和m(1≤n≤m≤500)——集合S中的元素数量和S中元素值的上限。
第二行包含n个整数S1, S2, …, Sn(1≤S1
输出数据格式:
输出一个整数——S变空所需的期望秒数,对1,000,000,007取模的结果。题目大意: 你有一个由n个不同的整数组成的集合S,这些整数介于1和m之间。每一秒钟你按照以下步骤操作: 1. 从S中均匀随机选择一个元素x。 2. 将x从S中移除。 3. 如果x+1≤m并且x+1不在S中,将x+1添加到S中。 问S变空所需的期望秒数是多少? 输出答案对1,000,000,007取模的结果。 输入数据格式: 第一行包含两个整数n和m(1≤n≤m≤500)——集合S中的元素数量和S中元素值的上限。 第二行包含n个整数S1, S2, …, Sn(1≤S1