题目描述
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} $ .
输入格式
$ 1 \leq n \leq m \leq 500,1 \leq S_1 < S_2 < \ldots < S_n \leq m $
见到 \(m\le 500\) 还愣了一下，没想到放了 \(m^3\) 过。
根据期望的线性性，考虑对某一个数消失的期望分开计算。
模拟一下发现，某一个数 \(a_i\) 不再加回集合的期望是只和 \(a_{i+1}\) 相关。尝试用一个 \(dp\) 去求出这个期望。
定义 \(dp_{i,j}\) 为现在 \(i\) 在走，下一个比他大的数是 \(j\) ，\(i\) 的期望步数。
\(dp_{i,m+1}=m+1-i,dp_{i,j}=(dp_{i+1,j}+dp_{i,j+1}+1)\times \frac 12\)
// LUOGU_RID: 122804271
#include<bits/stdc++.h>
using namespace std;
const int N=505,P=1e9+7,iv2=P+1>>1;
int dp[N][N],n,m,ans,s[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",s+i);
for(int i=m;i;i--)
{
for(int j=m+1;j>i;j--)
{
if(j<=m)
(dp[i][j]+=iv2*1LL*(dp[i+1][j]+dp[i][j+1]+1)%P)%=P;
else
dp[i][j]=dp[i+1][j]+1;
}
}
s[n+1]=m+1;
for(int i=1;i<=n;i++)
(ans+=dp[s[i]][s[i+1]])%=P;
printf("%d",ans);
}