วิธีทาสีภาพ N ภาพ ให้ภาพที่อยู่ติดกันไม่มีสีเหมือนกัน ในภาษา C

โจทย์ให้มีภาพจำนวน N ภาพ และมีสีทั้งหมด M สี ต้องการหาจำนวนวิธีในการทาสี ทำให้ภาพที่อยู่ติดกันไม่มีสีเหมือนกัน ผลลัพธ์อาจมีค่ามากมาก จึงคำนวณภายใต้โมดูล로 10⁹ + 7

สูตรการคำนวณ: Ways = M × (M-1)^N-1

ตัวอย่าง

Input: n = 5, m = 6

Output: 3750

โค้ดตัวอย่าง (C++)

#include <iostream>
#include <math.h>
#define MOD 1000000007
using namespace std;

unsigned long modPow(unsigned long x, unsigned long y, unsigned long p) {
    unsigned long res = 1;
    x = x % p;
    while (y > 0) {
        if (y & 1) res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}

int ways(int n, int m) {
    return (int)((modPow(m - 1, n - 1, MOD) * 1LL * m) % MOD);
}

int main() {
    int n = 5, m = 6;
    cout << "There are " << ways(n, m) << " ways";
    return 0;
}

ผลลัพธ์

There are 3750 ways