ในปัญหานี้ เราได้รับจำนวนเต็มสองจำนวน 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
