Trong bài toán này, chúng ta được cho hai số nguyên n và m, trong đó n là số bức tranh và m là số màu có sẵn. Nhiệm vụ của chúng tôi là tạo ra một chương trình sẽ tìm tổng số cách mà chúng tôi có thể vẽ các bức tranh sao cho không có bức tranh nào liên tiếp có cùng màu.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
n = 3, m =3
Đầu ra
12
Giải thích
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
Để giải quyết vấn đề này, chúng ta có thể vẽ tất cả n bức tranh với m màu, bây giờ các bức tranh tiếp theo có thể được vẽ bằng n-1 màu không kể màu đã dùng để vẽ bức tranh cuối cùng. Vì vậy, tổng số cách là,
n*(m-1)(n-1)
Chương trình cho thấy việc triển khai giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The number of ways to color the given paintings is : 9072