隣接する絵画がC++で同じ色にならないようにN枚の絵画をペイントする方法

この問題では、2つの整数nとmが与えられます。ここで、nは絵画の数、mは使用可能な色の数です。私たちの仕事は、連続する絵が同じ色にならないように絵を描くことができる方法の総数を見つけるプログラムを作成することです。

問題を理解するために例を見てみましょう

入力

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

この問題を解決するために、n個の絵すべてをm色でペイントできます。これで、最後の絵のペイントに使用した色を除いて、次の絵をn-1色でペイントできます。つまり、ウェイの総数は、

n*(m-1)(n-1)

ソリューションの実装を示すプログラム

例

#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