ルーレット [いろはちゃんコンテスト Day1 K]

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_k

解説

https://atcoder.jp/contests/iroha2019-day1/submissions/5196729

まず、各円盤では独立に確率が決められている。
真面目に計算するのではなく、線形性などをうまく利用するのだろうという感じで考える。
　
下の桁から順番に計算していこう。
p := ここまでの10の累乗の期待値
ある桁の期待値×pがその桁で得られる得点の期待値になる。
これは分配法則でばらしてみるとよく分かる。

p = 10*0.5+100*0.2+1000*0.3
ある桁の期待値 = 4*0.5 + 2*0.5
だったとき、
ある桁の期待値×p
= (10*0.5+100*0.2+1000*0.3)×(4*0.5 + 2*0.5)
= 40*0.25 + 400*0.1 + 4000*0.15 + 20*0.25 + 200*0.1 + 2000*0.15
となり、あり得るパターンとその確率の積の総和となるので、
これはその桁で得られる得点の期待値

　
これで順番に計算するだけ。
pもこの分配法則っぽくやれば更新できる。

int N;
int M[201010]; vector<int> A[201010];
//---------------------------------------------------------------------------------------------------
mint get(int x) {
	mint res = 1;
	while (0 < x) {
		res *= 10;
		x /= 10;
	}
	return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rrep(i, N-1, 0) {
		cin >> M[i];
		rep(j, 0, M[i]) {
			int x; cin >> x;
			A[i].push_back(x);
		}
	}
 
	mint ans = 0;
	mint p = 1;
	rep(i, 0, N) {
		mint sm = 0;
		fore(x, A[i]) sm += x;
		ans += sm * p / M[i];
 
		mint tot = 0;
		fore(x, A[i]) tot += get(x);
		p = tot * p / M[i];
	}
	rep(i, 0, N) ans *= M[i];
	cout << ans << endl;
}