Soluție HackerRank pentru Bridges and Harbors, subdomeniul Combinatorics, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Bridges and Harbors
- Domeniu: Combinatorics
- Limbaj: C++14
Challenge: Bridges and Harbors
Subdomeniu: Combinatorics (combinatorics)
Scor cont: 100.0 / 100
Submission status: Accepted
Submission score: 1.0
Submission ID: 464805645
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/bridges-and-harbors/problem
Cerință
DestinyLand is a really fun place for kids. It is composed of N islands, numbered from 1 to N. The company is planning to divide these N islands into exactly M area, such that, each island will belong to one of the M areas, and each area will contain at least one island.
Now the company is going to build bridges between the islands. Each area should be isolated from another. So the bridges can be built, only if both the endpoint islands belong to the same area. That is, in total they will build exactly _n-m_ bridges to maintain connectivity within each area. (Of course, they won't build more than _N-M_ bridges because that cost too much!)
For area to area connections, the company planned to build a harbor to one chosen island in each area. Due to heavy traffic, each of the chosen islands should NOT directly connect with more than K bridges. Can you help the company figure out how many bridge and harbor construction layouts are possible?
Note that all harbors are the same, all bridges are the same, but islands are distinct.
Input Format
The first line contains an integer T indicating the number of test cases.
For each test case, there are four space separated integers _N M K MOD_
Output Format
For each test case, print the number of layouts modulo MOD
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 10<sup>9</sup>
1 ≤ M , K ≤ min(N, 100)
1 ≤ MOD ≤ 2*10<sup>9</sup>
Sample Input
3
3 2 1 1000003
3 1 2 1234567891
3 1 1 314159
Sample Output
6
9
6
Cod sursă
#include <bits/stdc++.h>
using namespace std;
static const int PR[25] = {
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// factorial prime exponents for 0..100
int pref[101][25]{};
for (int i = 1; i <= 100; ++i) {
for (int j = 0; j < 25; ++j) pref[i][j] = pref[i - 1][j];
int x = i;
for (int j = 0; j < 25; ++j) {
while (x % PR[j] == 0) {
x /= PR[j];
pref[i][j]++;
}
}
}
auto comb_small_r = [&](long long n, int r, int MOD) -> int {
if (r < 0 || n < 0 || r > n) return 0;
if (r == 0) return 1 % MOD;
long long rr = min<long long>(r, n - r);
r = (int)rr;
if (r == 0) return 1 % MOD;
int need[25];
for (int j = 0; j < 25; ++j) need[j] = pref[r][j];
long long res = 1 % MOD;
for (long long t = n - r + 1; t <= n; ++t) {
long long x = t;
for (int j = 0; j < 25; ++j) {
int p = PR[j];
while (need[j] > 0 && x % p == 0) {
x /= p;
need[j]--;
}
}
res = (__int128)res * (x % MOD) % MOD;
}
for (int j = 0; j < 25; ++j) {
for (int e = 0; e < need[j]; ++e) {
res = (__int128)res * PR[j] % MOD;
}
}
return (int)res;
};
auto mod_pow = [&](long long a, long long e, int MOD) -> int {
if (MOD == 1) return 0;
long long r = 1 % MOD;
a %= MOD;
if (a < 0) a += MOD;
while (e > 0) {
if (e & 1LL) r = (__int128)r * a % MOD;
a = (__int128)a * a % MOD;
e >>= 1LL;
}
return (int)r;
};
int T;
cin >> T;
while (T--) {
long long N;
int M, K, MOD;
cin >> N >> M >> K >> MOD;
if (MOD == 1) {
cout << 0 << '\n';
continue;
}
if (N == M) {
cout << (1 % MOD) << '\n';
continue;
}
long long E = N - M; // total bridges
int D = (int)min<long long>(E, 1LL * K * M);
// comb[d][l] = C(E-d, l), d=0..D, l=0..K
vector<vector<int>> comb(D + 1, vector<int>(K + 1, 0));
for (int l = 0; l <= K; ++l) comb[0][l] = comb_small_r(E, l, MOD);
for (int d = 1; d <= D; ++d) {
comb[d][0] = 1 % MOD;
for (int l = 1; l <= K; ++l) {
int v = comb[d - 1][l] - comb[d][l - 1];
if (v < 0) v += MOD;
comb[d][l] = v;
}
}
int d0max = (int)min<long long>(D, 1LL * K * M);
vector<int> prev(D + K + 2, 0), cur(D + K + 2, 0);
// j=0: foo(i,0)=(N-M)^i, where i=E-d
for (int d = 0; d <= d0max; ++d) {
prev[d] = mod_pow(E, E - d, MOD);
}
// j = 1..M-1
for (int j = 1; j <= M - 1; ++j) {
int curMax = (int)min<long long>(D, 1LL * K * (M - j));
int prevMax = (int)min<long long>(D, 1LL * K * (M - (j - 1)));
fill(cur.begin(), cur.end(), 0);
for (int d = curMax; d >= 0; --d) {
long long s = 0;
int lim = min(K, D - d);
for (int l = 0; l <= lim; ++l) {
int dd = d + l;
if (dd > prevMax) break;
s += 1LL * comb[d][l] * prev[dd];
if (s >= (1LL << 62)) s %= MOD;
}
cur[d] = (int)(s % MOD);
}
prev.swap(cur);
}
long long ans = 0;
int lim = (int)min<long long>(K, E);
// C(E-1,u-1) = comb[1][u-1]
if (E >= 1) {
for (int u = 1; u <= lim; ++u) {
int waysChoose = (u - 1 <= K ? comb[1][u - 1] : comb_small_r(E - 1, u - 1, MOD));
ans += 1LL * waysChoose * prev[u];
if (ans >= (1LL << 62)) ans %= MOD;
}
}
ans %= MOD;
ans = ans * (M % MOD) % MOD;
ans = ans * comb_small_r(N, M, MOD) % MOD;
cout << ans % MOD << '\n';
}
return 0;
}