Codeforces #889 : Div1 C. Expected Destruction

これは割とすんなり解いてるな。
https://codeforces.com/contest/1854/problem/C

問題

1～Mの値をとる整数集合Sが与えられる。
Sが空でない限り、以下を行う。

• Sのうち1要素を等確率で選ぶ。その値をxとする。
• Sからxを取り除く。そしてx+1≦MかつSに(x+1)がないなら、Sに(x+1)を加える。

Sが空になるまでに行う操作回数の期待値を求めよ。

解法

1～(M+1)のマスからなる双六を考える。
Sに相当する各マスと(M+1)番のマスにコマを置く。
この時、(M+1)番以外のいずれかのコマを等確率で選び、1つ進める。ただし移動先に他のコマがあれば片方取り除く。

上記のように考えると、各コマが取り除かれるまでに移動する回数=前のコマに追い付くまでの移動回数の期待値をそれぞれ求めればよい。

int N,M;
int S[555];
const ll mo=1000000007;

ll memo[505][505];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}
ll hoge(int a,int b) {
	if(memo[a][b]>=0) return memo[a][b];
	if(a==b) return 0;
	if(a==0) return b;
	
	ll ret=(hoge(a-1,b)+1+hoge(a,b-1))*modpow(2)%mo;
	return memo[a][b]=ret;
	
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(memo);
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>S[i];
		S[i]--;
	}
	S[N]=M;
	ll ret=0;
	FOR(i,N) ret+=hoge(M-S[i+1],M-S[i]);
	cout<<ret%mo<<endl;
}

まとめ

コードも短いしサクサク解けて良かったね。