C++-Programm zum Zählen der Anzahl von Farbschemata, die zwei Bedingungen erfüllen

Angenommen, wir haben drei Zahlen N, M und K. Stellen Sie sich vor, es gibt N Blöcke, die in einer Reihe angeordnet sind. Wir betrachten die folgenden zwei Arten der Färbung. Zwei Blöcke sind genau dann unterschiedlich gefärbt, wenn die Blöcke auf die folgenden zwei Arten in unterschiedlichen Farben gefärbt sind: -

• Für jeden Block wird er mit einer der M-Farben gefärbt (es müssen nicht alle Farben verwendet werden)

• Es dürfen höchstens K Paare benachbarter Blöcke mit der gleichen Farbe vorhanden sein

Wenn die Antwort zu groß ist, wird das Ergebnis Modulo 998244353 zurückgegeben.

Wenn die Eingabe also N = 3; M = 1 ist, ist die Ausgabe 6, da wir die folgenden verschiedenen Formate einfärben können: 112, 121, 122, 211, 212 und 221.

Schritte

Um dieses Problem zu lösen, folgen wir den folgenden Schritten:

maxm := 2^6 + 5
p := 998244353
Define two large arrays fac and inv or size maxm
Define a function ppow(), this will take a, b, p,
ans := 1 mod p
a := a mod p
while b is non-zero, do:
   if b is odd, then:
      ans := ans * a mod p
   a := a * a mod p
   b := b/2
return ans
Define a function C(), this will take n, m,
if m < 0 or m > n, then:
   return 0
return fac[n] * inv[m] mod p * inv[n - m] mod p
From the main method, do the following
fac[0] := 1
for initialize i := 1, when i < maxm, update (increase i by 1), do:
   fac[i] := fac[i - 1] * i mod p
inv[maxm - 1] := ppow(fac[maxm - 1], p - 2, p)
for initialize i := maxm - 2, when i >= 0, update (decrease i by 1), do:
   inv[i] := (i + 1) * inv[i + 1] mod p
ans := 0
for initialize i := 0, when i <= k, update (increase i by 1), do:
   t := C(n - 1, i)
   tt := m * ppow(m - 1, n - i - 1, p)
   ans := (ans + t * tt mod p) mod p
return ans

Beispiel

Sehen wir uns zum besseren Verständnis die Implementierung unten an −

#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;
}

Eingabe

3, 2, 1

Ausgabe

6

Das obige ist der detaillierte Inhalt vonC++-Programm zum Zählen der Anzahl von Farbschemata, die zwei Bedingungen erfüllen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!