C++で長さLの文字列における魔法のペア（マジカルペア）の数を求める方法

2つの文字列 str1 と str2 が与えられたとき、長さLの「魔法のペア」の数を求める問題を考えてみましょう。すべてのインデックス i について str1[i] < str2[i] が成り立つとき、この2つの文字列は魔法のペアであると定義されます。ペアの総数は非常に大きな値になる可能性があるため、答えは 10⁹ を法とした剰余として返します。なお、文字列には小文字の英字のみが含まれるものとします。

考え方

この問題のアプローチはシンプルです。まず長さ L = 1 の場合を考えてみます。インデックス i = 1 の位置にある str1 の文字が 'a' であるとき、対応する str2 の文字は 'b' から 'z' までの25通りから選ぶことができます。次に str1 の文字が 'b' であれば、str2 は 'c' 以降の24通りとなり、以下同様に選択肢が1つずつ減っていきます。

したがって、1文字あたりの組み合わせの総数は次のように計算できます。

25 + 24 + … + 1 = 325

長さ L = 2 の場合は、各位置の選択が互いに独立しているため、組み合わせの総数は 325² となります。一般化すると、長さ L のときの答えは 325^L です。この値は指数関数的に増大するため、実際の計算では 10⁹ で割った余りを求めます。

べき乗の計算には繰り返し二乗法（バイナリ累乗法）を用いることで、時間計算量 O(log L) で効率的に結果を得られます。

実装例

#include<iostream>
#include<cmath>
using namespace std;
int power(int a, unsigned int b, int mod) {
    int res = 1;
    a = a % mod;
    while (b > 0) {
        if (b & 1)
            res = (res * a) % mod;
        b = b >> 1;
        a = (a * a) % mod;
    }
    return res;
}
int main() {
    int L = 2, P = pow(10, 9);
    int res = power(325, L, P);
    cout << "Combinations: " << res << endl;
}

出力

Combinations: 105625

まとめ

長さLの魔法のペアの総数は、1文字あたり325通りの組み合わせを基に 325^L という式で表せることが分かりました。繰り返し二乗法とモジュロ演算を組み合わせることで、L が非常に大きい場合でもオーバーフローを防ぎながら高速に答えを計算することができます。