http://codeforces.com/contest/935/problem/D
M種類の文字があり、文字1～文字Mである。
N文字の文字列AとBがある。
この2つの文字列は一部文字が欠けており、その部分は0となっている。
0となっている部分がk個ある場合には文字の入り方次第でM^k通り考えられるが、その中で辞書順としてA>Bとなる確率を求めよ（mod10^9+7で）。
解法
http://codeforces.com/contest/935/submission/35490328
本当のsubmitではsame配列が入っているが、使わなかったので、下のコードでは消してある。
確率を求めよとあるが、後でM^kで割ればいいので、辞書順としてA>Bとなる組合せを計算していこう。
その前にzero配列を構築する。
zero[i] := 文字列A,Bの範囲[i,N-1]に含まれるゼロの数
先頭から文字を確定していく。
i番目の文字を確定していくときに、[1,i)番目の文字の状況は3つ考えられる。
- 既にA＜BならどうやってもA
- A=Bなら、今後の確定によって辞書順が変わる可能性があるので、確定を続ける
- A＞BならどうやってもA＞Bは覆らないので、それ以降のゼロの数をtとすると、その後はM^t通り全てでA＞Bとなる
よって確定を進めていくが、A=Bであることを保ちながら、確定していく。
「cmb := これまでの2つの文字列のprefix（[0,i)番目のこと）が同じとなる組合せ」として、これを使っていく。
まずA[i]もB[i]も定まっている場合。
違っているなら、これ以降の確定は無意味なので、終了するが、A[i]＞B[i]ならA＞Bが達成できるので、cmb*M^zero[i+1]を答えに加える。
同じなら、A,Bのprefixは同じとなるので、cmb *= 1で続ける
両方欠けている場合。
A＞Bとなる場合はC(M,2)通りあるので、C(M,2)*M^zero[i+1]通りを答えに加える。
cmbも更新するが、A=BとなるにはM通りの割り当て方法があるので、cmb*=Mとする
片方欠けている場合。
A>Bと出来るなら、(その通り数)*M^zero[i+1]通りを答えに加える。
cmbも更新するが、A=Bとなるのは1通りだけなので、cmb*=1
最後に答えをM^zero[0]で割って答え。
Comb<mint, 201010> com; int N, M; int A[101010], B[101010]; int zero[101010]; // zero[i] := [i,N-1]でのA,Bのゼロの数 //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M; rep(i, 0, N) cin >> A[i]; rep(i, 0, N) cin >> B[i]; rrep(i, N - 1, 0) { zero[i] = zero[i + 1]; if (A[i] == 0) zero[i]++; if (B[i] == 0) zero[i]++; } mint ans = 0; mint cmb = 1; // これまでを同じにする組み合わせ数 rep(i, 0, N) { if (A[i] != 0 and B[i] != 0) { if (A[i] != B[i]) { if (A[i] > B[i]) ans += cmb * (mint(M) ^ zero[i + 1]); break; } } else if (A[i] == 0 and B[i] == 0) { // A[i] > B[i]とした場合 ans += cmb * com.aCb(M, 2) * (mint(M) ^ zero[i + 1]); // A[i] == B[i]とした場合 cmb *= M; } else if (A[i] == 0) { // A[i] > B[i]とした場合 ans += cmb * mint(M - B[i]) * (mint(M) ^ zero[i + 1]); // A[i] == B[i]とした場合 // 何もしない } else if (B[i] == 0) { // A[i] > B[i]とした場合 ans += cmb * mint(A[i] - 1) * (mint(M) ^ zero[i + 1]); // A[i] == B[i]とした場合 // 何もしない } } ans /= mint(M) ^ zero[0]; cout << ans << endl; }
