[AtCoder] M-SOLUTIONS プロコンオープン C – Best-of-(2n-1)

2019年6月3日2019年6月28日

問題

方針

拡張ユークリッドの互除法

\( d = 10^9 + 7 \) とします。

\[ RQ \equiv P \ (\bmod d)\]

上記を満たすような \( R \) をどのように求めるかですが、次の方程式を考えます。

\[ ax \bmod d = b \bmod d \]

ここで、変数 \( s, t \) を用いて、

\[ as + dt = 1 \]

を満たす変数 \( s, t \) の組を一つ見つけます。これは拡張ユークリッドの互除法を用いて求めることができます。 上式の両辺に \( b \) を掛けて、\( d \) で \( \bmod \) を取ると、\( dbt \bmod d = 0 \) より、

\[ asb \bmod d = b \bmod d \]

となるので、\( x = sb \) となります。

また、あまり理解していないんですが、\( R \) は、

\[ R = \dfrac{P}{Q} \bmod d \]

と計算できるようです。\( \dfrac{1}{Q} \bmod d\) については、よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方が詳しいです。

高橋君が最終的に勝利するときのゲーム数の期待値を求める

高橋君が最終的に勝利するときのゲーム数の期待値を求めます。高橋君が勝利した時のゲーム数を \( L \) とします。ここで、\( N \leq L \) を満たすことに注意します。

高橋君が最終的に勝利するとき、青木君が勝つゲームの回数

高橋君が最終的に勝利するとき、青木君が勝つゲームの回数を \( k \ ( 0 \leq k \leq N – 1) \) とします。このとき、引き分けの回数は、\( 0 \) 以上の数となります。長さ \( L \) のゲームにおいて、\( L \) 回目のゲームでは必ず高橋君が勝つことに注意すると、青木君が \( k \) 回勝つときの期待値 \( E[X_k]\) は、

\[ E[X_k] = \left(\dfrac{A}{100} \right)^{N} \cdot  \sum_{i = k}^{\infty} (i + N) \cdot {}_{N + i – 1} \mathrm{ C }_k \cdot \left( \dfrac{B}{100} \right)^{k} \cdot  {}_{N + i – 1 – k} \mathrm{ C }_{i – k} \cdot \left ( \dfrac{C}{100}\right )^{i – k} \]

となります。これは、\( i + N \) 回のゲームで青木君が \( k \) 回勝ち、引き分けが \( i \) 回起きた時の期待値を意味します。無限等比級数の和が出てきてしまいましたが、Wolfram Alpha で次の計算を行うと、

\[
\begin{eqnarray}
f(k) &=& \sum_{i = k}^{\infty} (i + N) \cdot \ {}_{N + i – 1} \mathrm{ C }_k \cdot {}_{N + i – 1 – k} \mathrm{ C }_{i – k} \cdot p^{i – k}\\
&=& \dfrac{Np \cdot {}_{N + k} \mathrm{C}_{k} + (N + k)(1-p) \cdot {}_{N + k – 1} \mathrm{C}_{k}}{(1 – p)^{N + k + 1}}
\end{eqnarray}
\]

が得られます。具体的には、"[sum (i + N) * C(N + i – 1, k)* (q)^{k} * C(N + i – 1 – k, i – k ) * p^{i – k}, {i, k, infinity}]" を実行します。

高橋君が最終的に勝利するときのゲーム数の期待値

高橋君が最終的に勝利するときのゲーム数の期待値 を \( E[X] \) とすると、上記の結果から、

\[
\begin{eqnarray}
E[X] &=& \sum_{k = 0}^{N – 1} E[X_k]\\
&=& A^{N} \cdot \sum_{k = 0}^{N – 1} B^{k} \cdot \dfrac{NC \cdot {}_{N + k} \mathrm{C}_{k} + (N + k)(100 – C) \cdot {}_{N + k – 1} \mathrm{C}_{k}}{(100 – C)^{N + k + 1}}
\end{eqnarray}
\]

となります。計算としては、\( p = \dfrac{C}{100} \) としています。

ゲーム回数の期待値

同様にして、青木君が最終的に勝利するときを考慮すると、ゲーム回数の期待値 \( E[Y]\) は、

\[ E[Y] = A^{N} \cdot \sum_{k = 0}^{N – 1} B^{k} \cdot \dfrac{NC \cdot {}_{N + k} \mathrm{C}_{k} + (N + k)(100 – C) \cdot {}_{N + k – 1} \mathrm{C}_{k}}{(100 – C)^{N + k + 1}} \\ + B^{N} \cdot \sum_{k = 0}^{N – 1} A^{k} \cdot \dfrac{NC \cdot {}_{N + k} \mathrm{C}_{k} + (N + k)(100 – C) \cdot {}_{N + k – 1} \mathrm{C}_{k}}{(100 – C)^{N + k + 1}}\]

となります。

コード

提出したコード

逆元など (けんちょんさんのコード)

typedef long long ll;

// a^n mod を計算する
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// a^{-1} mod を計算する
ll modinv(ll a, ll mod) {
    return modpow(a, mod - 2, mod);
}

const int MAX = 510000;
const int MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}