C++ প্রোগ্রাম: ব্লক রঙ করার উপায় সংখ্যা গণনা (দুটি শর্তে)

মান লিখুন: আমাদের কাছে তিনটি সংখ্যা N, M এবং K রয়েছে। Nটি ব্লক সারিয়ে আছে। ব্লকগুলো রঙ করার দুটি নিয়ম:

প্রতিটি ব্লকের জন্য Mটি রঙের যেকোনো একটি ব্যবহার করুন (সব রঙ ব্যবহার করা বাধ্যতামূলক নয়)
সর্বোচ্চ K জোড়া সন্নিহিত ব্লক একই রঙের হতে পারে

উত্তর বড় হলে ৯৯৮২৪৪৩৫৩ দিয়ে মডুলো নিয়ে ফলাফল দিন।

উদাহরণ

যদি ইনপুট হয় N = 3; M = 2; K = 1, তবে আউটপুট হবে 6, কারণ রঙ করার উপায়গুলো: 112, 121, 122, 211, 212, 221।

সমাধানের ধাপসমূহ

maxm := 2×10⁶ + 5
p := 998244353
fac এবং inv অ্যারে (আকার maxm)
ppow(a, b, p) ফাংশন: a^b mod p বের করুন
C(n, m) ফাংশন: কম্বিনেশন বের করুন
মূল ফাংশন থেকে:
    fac[0] := 1
    for i := 1 থেকে maxm-1: fac[i] := fac[i-1] * i mod p
    inv[maxm-1] := ppow(fac[maxm-1], p-2, p)
    for i := maxm-2 থেকে 0: inv[i] := (i+1) * inv[i+1] mod p
    ans := 0
    for i := 0 থেকে k:
        t := C(n-1, i)
        tt := m * ppow(m-1, n-i-1, p) mod 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, M = 2, K = 1;
    cout << solve(N, M, K) << endl;
}

ইনপুট

3, 2, 1