C++でクイズゲームに勝つために必要な最小プレイヤー数を求める方法

問題文

N問の質問があり、それぞれの質問にはK個の選択肢が用意されています(1 <= N <= 1000000000、1 <= K <= 1000000000)。この問題では、1番目から順にすべての問題をクリアしていき、なんとかしてゲームに勝つために必要な「各問題に挑戦したプレイヤー数の総和」の最小値を求めます。ただし、答えは10⁹+7で割った余りとして出力してください。

重要なルールとして、一度でも誤答をするとそのプレイヤーは即座に脱落してしまう点に注意しましょう。

例

N = 5、K = 2 の場合、答えは 62 となります。

アルゴリズム

• N番目の問題を解くためには、K人のプレイヤーが必要です。
• (N−1)番目の問題を解くためには、K²人のプレイヤーが必要です。
• 同様に遡っていくと、1番目の問題を解くためにはK^N人のプレイヤーが必要になります。
• したがって、この問題は等比数列の和「K + K² + … + K^N」を求める問題に帰着できます。この和は次の式で表されます。
  K × (K^N − 1) ÷ (K − 1)

C++での実装例

NとKは最大10億まであり得るため、べき乗を素朴に計算するとオーバーフローや計算時間の問題が発生します。そこで、以下の2つのテクニックを組み合わせます。

• 繰り返し二乗法(バイナリ累乗):べき乗をO(log N)回程度の掛け算で高速に求めます。
• フェルマーの小定理による逆元:剰余演算の中では直接割り算ができないため、「(K − 1)^MOD−2 を掛ける」という形で除算を置き換えます。

#include <iostream>
#include <cmath>
#define MOD 1000000007
using namespace std;
long long int power(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) {
            res = res * a;
            res = res % MOD;
        }
        b = b / 2;
        a = a * a;
        a = a % MOD;
    }
    return res;
}
long long getMinPlayer(long long n, long long k) {
    long long num = ((power(k, n) - 1) + MOD) % MOD;
    long long den = (power(k - 1, MOD - 2) + MOD) % MOD;
    long long ans = (((num * den) % MOD) * k) % MOD;
    return ans;
}
int main() {
    long long n = 5, k = 2;
    cout << "Minimum players = " << getMinPlayer(n, k) << endl;
    return 0;
}

コードの解説

getMinPlayer関数では、まず分子となる「K^N − 1」を繰り返し二乗法で計算します。続いて分母「K − 1」については、フェルマーの小定理を利用して逆元(MOD−2乗)を求めることで、剰余演算下での除算を実現しています。最後にKを掛け合わせることで、等比数列の和全体を正しく剰余込みで算出しています。

出力

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

Minimum players = 62