CodeTON Round 5 : G. Tenzing and Random Operations

ここまで来てだいぶコードが短い。
https://codeforces.com/contest/1842/problem/G

問題

N要素の整数列Aと、正整数M,Vが与えられる。

以下の処理をM回行う。

• 0～(N-1)のうちiを等確率で選び、i以上N未満のjに対しA[j]にVを加算する

Aの積の期待値を求めよ。

解法

X(j,i) := i回目の処理で、A[j]に加算された値
とすると、求めるのは となる。
これらの積を取る場合に、A[i]を取る部分とX(j,i)の積を取ることを考える。

sum(X(j,i))の部分は容易に計算できるの意で、DPでこれらの積を計算していく際、
dp(n,m) := 先頭n項の積を取ったとき、A_i側を掛けた回数がmの時の積和
として計算していこう。

int N,M,V;
ll from[5555],to[5555];
const ll mo=1000000007;

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;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>V;
	from[0]=1;
	
	for(i=1;i<=N;i++) {
		int A;
		cin>>A;
		ll p=i*modpow(N)%mo*V%mo;
		ZERO(to);
		FOR(j,i) {
			(to[j+1]+=from[j]*p%mo*(M-j))%=mo;
			(to[j]+=from[j]*(A+1LL*j*V%mo))%=mo;
		}
		swap(from,to);
	}
	ll ret=0;
	FOR(i,N+1) ret+=from[i];
	cout<<ret%mo<<endl;
	
}

まとめ

本番でさらっとこの回答に至れるかな…。