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