Số cách tô N bức tranh sao cho tranh liền kề khác màu trong C

Cho N bức tranh và M màu. Cần tìm số cách tô màu sao cho không có hai bức tranh liền kề cùng màu. Kết quả có thể rất lớn nên tính modulo 10⁹ + 7.

Công thức: Ways = M × (M-1)N-1

Ví dụ

Đầu vào: n = 5, m = 6

Đầu ra: 3750

#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 modPow(m - 1, n - 1, MOD) * m % MOD;
}

int main() {
    int n = 5, m = 6;
    cout << "Co " << ways(n, m) << " cach to mau";
    return 0;
}

Kết quả

Co 3750 cach to mau