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
Cerinta
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
6Cod sursa
#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;
}
HackerRank Combinatorics – Bridges and Harbors