โปรแกรม C++ นับวิธีทาสีบล็อกด้วยเงื่อนไข 2 ข้อ

คำอธิบายปัญหา

สมมติว่าเรามีตัวเลข 3 ตัวคือ N, M และ K มีบล็อก N ชิ้นจัดเรียงเป็นแถว มี 2 วิธีการทาสี:

• แต่ละบล็อกใช้สี 1 ใน M สี (ไม่บังคับใช้หมด)
• มีคู่บล็อกติดกันที่ทาสีเหมือนกันได้สูงสุด K คู่

ตัวอย่าง: N = 3; M = 2; K = 1 ผลลัพธ์คือ 6 วิธี คือ 112, 121, 122, 211, 212, 221

ขั้นตอนการแก้ปัญหา

maxm := 2^6 + 5
p := 998244353
กำหนดอาร์เรย์ fac และ inv ขนาด maxm
ฟังก์ชัน ppow(a, b, p) คำนวณ a^b mod p
ฟังก์ชัน C(n, m) คำนวณ nCm mod p
จาก main:
    fac[0] := 1
    สำหรับ i := 1 ถึง maxm-1: fac[i] := fac[i-1] * i mod p
    inv[maxm-1] := ppow(fac[maxm-1], p-2, p)
    สำหรับ i := maxm-2 ถึง 0: inv[i] := (i+1) * inv[i+1] mod p
    ans := 0
    สำหรับ i := 0 ถึง k:
        t := C(n-1, i)
        tt := m * ppow(m-1, n-i-1, p)
        ans := (ans + t * tt mod p) mod p
    คืนค่า ans

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

#include <bits/stdc++.h>
using namespace std;

const long maxm = 2e6 + 5;
const long p = 998244353;
long fac[maxm], inv[maxm];

long ppow(long a, long b, long p){
    long ans = 1 % p;
    a %= p;
    while (b){
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

long C(long n, long m){
    if (m < 0 || m > n) return 0;
    return fac[n] * inv[m] % p * inv[n - m] % p;
}

long solve(long n, long m, long k){
    fac[0] = 1;
    for (long i = 1; i < maxm; i++) fac[i] = fac[i - 1] * i % p;
    inv[maxm - 1] = ppow(fac[maxm - 1], p - 2, p);
    for (long i = maxm - 2; i >= 0; i--) inv[i] = (i + 1) * inv[i + 1] % p;
    long ans = 0;
    for (long i = 0; i <= k; i++){
        long t = C(n - 1, i);
        long tt = m * ppow(m - 1, n - i - 1, p) % p;
        ans = (ans + t * tt % p) % p;
    }
    return ans;
}

int main(){
    int N = 3;
    int M = 2;
    int K = 1;
    cout << solve(N, M, K) << endl;
}

อินพุต

3, 2, 1

เอาต์พุต

6