C++で隣り合う絵が同じ色にならないようにN枚の絵を描く組み合わせの数を求める方法

問題の概要

この問題では、N枚の絵とM色の絵の具が与えられ、「隣り合う2枚の絵が同じ色にならないように」描く方法が全部で何通りあるかを求めます。

答えとなる値は非常に大きくなる可能性があるため、そのまま扱うのは困難です。そこで、標準的な手法として 10⁹ + 7 を法とした剰余(モジュロ)で計算を行います。

組み合わせの数を求める公式

隣接する絵同士が同じ色にならないように塗る場合の総数は、次の式で求められます。

Ways = m × (m − 1)(n − 1)

この式の理屈はシンプルです。まず1枚目の絵には全てのM色から自由に色を選べますが、2枚目以降の各絵は「直前の絵と異なる色」でなければならないため、選べる色は常に(M − 1)色に制限されます。これをN枚分繰り返すことで上記の公式が導かれます。

入出力例

必要な入力は、絵の枚数 n と色の数 m です。

入力:

n = 5 , m = 6

出力:

3750

n=5、m=6 の場合は「6 × 5⁴ = 3750」となり、3750通りの描き方が存在することがわかります。

C++による実装例

巨大なべき乗を効率よく計算するために、繰り返し二乗法(バイナリ法)を利用します。このアルゴリズムを使えば、べき乗の剰余を O(log n) の時間計算量で高速に求めることができます。

#include <iostream>
#include <math.h>
#define modd 1000000007
using namespace std;

// 繰り返し二乗法による冪乗剰余の計算
unsigned long power(unsigned long x,
unsigned long y, unsigned long p) {
   unsigned long res = 1;
   x = x % p;
   while (y > 0) {
      if (y & 1)
         res = (res * x) % p;
      y = y >> 1;
      x = (x * x) % p;
   }
   return res;
}

// 塗り方の総数を求める関数
int ways(int n, int m) {
   return power(m - 1, n - 1, modd) * m % modd;
}

int main() {
   int n = 5, m = 6;
   cout << "There are " << ways(n, m) << " ways";
   return 0;
}

実行結果

There are 3750 ways

コードのポイント

• power関数: 指数 y をビットごとに右シフトしながら処理することで、x の y 乗を p で割った余りを高速に計算します。
• ways関数: 公式「m × (m−1)⁽ⁿ⁻¹⁾」に基づき、(m−1) の (n−1) 乗に m を掛け、最後に 10⁹+7 で剰余を取って答えを返します。
• オーバーフロー対策: 各段階で剰余を取ることで、非常に大きな値でも安全に計算できます。