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ụ là tạo chương trình tìm tổng số cách tô màu các bức tranh sao cho không có hai bức tranh liên tiếp cùng màu.
Hãy xem ví dụ để hiểu bài toá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 bài toán này, chúng ta có thể tô tất cả n bức tranh với m màu, bức tranh tiếp theo có thể tô bằng n-1 màu trừ màu dùng cho bức tranh cuối. Vì vậy, tổng số cách là,
n*(m-1)(n-1)
Chương trình triển khai giải pháp của chúng ta,
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<<"Số cách tô màu các bức tranh cho trước là : "<<colorPainting(n, m); return 0; }Đầu ra
Số cách tô màu các bức tranh cho trước là : 9072