隣り合う絵画が同じ色にならないようにC++でN枚の絵画を塗る方法の総数を求める

この記事では、整数 n と m が与えられたとき、n 枚の絵画を m 色の中から選んで塗り分ける方法が全部で何通りあるかを求める問題を扱います。ただし、隣り合う2枚の絵画に同じ色を使ってはいけないという制約があります。全探索ではなく、数学的な性質を活かした効率的な解法をC++で実装していきましょう。

まず、具体例で問題を確認します。

入力

n = 3, m = 3

出力

12

説明

P1 P2 P3
C1 C2 C3
C1 C3 C2
C1 C2 C1
C1 C3 C1
C2 C1 C2
C2 C3 C2
C2 C1 C3
C2 C3 C1
C3 C1 C3
C3 C2 C3
C3 C1 C2
C3 C2 C1

3枚の絵画（P1〜P3）に対して3色（C1〜C3）を使用し、隣接する絵画が必ず異なる色になるように塗ると、上記の12通りが存在します。

解法のアプローチ

この問題は積の法則（掛け算の原理）を使えばシンプルに解くことができます。

• 最初の絵画は m 色の中から自由に選べるため、m 通りの選択肢があります。
• 2枚目以降の各絵画は、直前の絵画と同じ色にできないため、残りの(m − 1) 通りの選択肢しかありません。

したがって、塗り方の総数は次の式で表されます。

m × (m − 1)(n − 1)

なお、n や m が大きくなると答えは膨大な値になるため、競技プログラミングでは通常 1000000007（10⁹ + 7）のような素数で剰余を取ります。べき乗の計算には繰り返し二乗法（バイナリ累乗）を採用することで、O(log n) という高速な時間計算量で処理できます。

C++での実装例

#include <iostream>
#define modd 1000000007
using namespace std;
unsigned long calcPower(unsigned long base, unsigned long power, unsigned long p){
    unsigned long result = 1;
    base = base % p;
    while (power > 0) {
        if (power & 1)
            result = (result * base) % p;
        power = power >> 1;
        base = (base * base) % p;
    }
    return result;
}
int colorPainting(int n, int m){
    return calcPower(m - 1, n - 1, modd) * m % modd;
}
int main(){
    int n = 5, m = 7;
    cout<<"The number of ways to color the given paintings is : "<<colorPainting(n, m);
    return 0;
}

出力

The number of ways to color the given paintings is : 9072

コードのポイント

• calcPower関数：繰り返し二乗法により (m − 1)^{(n − 1)} mod 1000000007 を効率的に計算します。指数を右シフトしながら、ビットが立っているときだけ結果に底を掛けることで高速化しています。
• colorPainting関数：数式「m × (m − 1)^{(n − 1)}」に基づき、最初の絵画の選択肢 m を掛けて最終的な答えを返します。

検算

n = 5、m = 7 の場合、7 × 6⁴ = 7 × 1296 = 9072 となり、プログラムの出力と一致します。また、冒頭の例 n = 3、m = 3 では 3 × 2² = 12 となり、こちらも一致します。

計算量

• 時間計算量：O(log n) — 繰り返し二乗法によるべき乗計算が支配的です。
• 空間計算量：O(1) — 追加で使用するメモリは定数個の変数のみです。