이 문제에서 두 개의 정수 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