Soluție HackerRank pentru Byteland Itinerary, subdomeniul Combinatorics, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Byteland Itinerary
- Domeniu: Combinatorics
- Limbaj: C++14
Challenge: Byteland Itinerary
Subdomeniu: Combinatorics (combinatorics)
Scor cont: 100.0 / 100
Submission status: Accepted
Submission score: 1.0
Submission ID: 464775094
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/byteland-itinerary/problem
Cerință
###A Byteland Vacation
You're planning a vacation to Byteland. It has m cities, and you can travel between cities either by *plane* or by *car*. There are exactly k highways in Byteland, and highway i connects cities a_i and b_i. If you want to travel from some city u to some city v and there is no highway between them, you can travel the distance from u to v by plane.
One curious feature of Byteland is that *the number of highways connecting some city to others is equal for each city in Byteland*. More formally, let deg_u be the number of cities such that there is a highway directly connecting city u to some city, v. deg_u = deg_v for all 1 ≤ u, v ≤ m.
You want to finalize the itinerary for your Byteland vacation. You decide to visit a sequence of n cities, A, such that 1 ≤ a_i ≤ m. During your trip, you'll visit each city in the sequence A = {a_1, a_2, …, a_n}; first traveling to city a_1, then traveling from a_1 to a_2, then traveling from a_2 to a_3, …, finally traveling from a_n-1 to a_n. Be aware that you *may end up visiting certain cities more than once*.
###Exciting Roads
There are two ways to travel from a_i to a_i + 1: by plane or by car. However, your preference is to travel by car because you dislike going through airport security and waiting in endless lines.
We call a continuous subsequence, (l, r), of A *exciting* if you can travel all the cities from a_l to a_r by car. More formally, (l, r) is exciting if for each l ≤ i ≤ r - 1 there is a highway between a_i and a_i + 1 (note that a_i must not be equal to a_i + 1).
We call r - l + 1 the *length* of continuous subsequence (l, r). You want to maximize the length of maximum exciting subsequence of A.
###Task
You decide to take a random itinerary, A (recall that |A| = n, and each a_i is a random city from 1 to m) and follow it. You want to know the expected maximum length of a continuous exciting subsequence in your itinerary.
Input Format
The first line contains three space-seperated non-negative integers describing the respective values of n (the number of cities in your itinerary), m (the number of cities in Byteland), and k (the number of highways in Byteland).
Each line i of the k subsequent lines contain two space-separated positive integers describing the respective cities, a_i and b_i, connected by highway i in Byteland.
Output Format
Let the answer be an irreducible fraction, (p / q). Print the result of (p · q^-1) mod (10^9 + 7).
Sample Input 0
3 2 0
Sample Output 0
1
Explanation 0
There are no roads, meaning that all the exciting subsequences have length 1. The expected length is also 1.
Sample Input 1
3 3 3
1 2
2 3
3 1
Sample Output 1
333333338
Explanation 1
There are exactly 27 different plans and there are highways connecting all the cities. There are 3 sequences with maximum length of exciting subsequence 1, 12 sequences with maximum length of exciting subseqence 2 and 12 sequences with maximum length of exciting subsequence 3.
The expected value of maximum length: E = (1 · 3 + 2 · 12 + 3 · 12) / 3^3 = 63 / 27 = 7 / 3.
That means, we need to print 7 · 3^(-1) modulo (10^9+7) = 333333338. 3^(-1) means [Modulo inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) here.
Constraints
- 1 ≤ n, m ≤ 10^5
- 0 ≤ k ≤ 10^6
- 1 ≤ a_i, b_i ≤ m, a_i ne b_i
- There are no loops and no multiple edges in Byteland road graph.
- All roads are undirected.
- Test cases with n, m ≤ 10 are 10% of the total score.
- Test cases with n, m ≤ 100 are 25% of the total score
- Test cases with n, m ≤ 1000 are 50% of the total score
Cod sursă
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int inf = (1 << 30) - 1;
const int64 linf = (1ll << 62) - 1;
const int N = 3e5 + 100;
const int M = 1e9 + 7;
int n, m, k;
int fact[N], ifact[N];
inline int power(int a, int b){
int res = 1;
for(; b; b >>= 1){
if(b & 1){
res = (1ll * res * a) % M;
}
a = (1ll * a * a) % M;
}
return res;
}
inline int inv(int x){
return power(x, M - 2);
}
inline void precalc(){
fact[0] = ifact[0] = 1;
for(int i = 1; i < N; i++){
fact[i] = (1ll * fact[i - 1] * i) % M;
ifact[i] = (1ll * ifact[i - 1] * inv(i)) % M;
}
}
inline int cnk(int n, int k){
if(k < 0 || k > n){
return 0;
}
int cur1 = (1ll * fact[n] * ifact[k]) % M;
return (1ll * cur1 * ifact[n - k]) % M;
}
int main(){
precalc();
cin >> n >> m >> k;
k = k * 2 / m;
int ans = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j * i <= n - 1; j++){
int cur1 = (1ll * power(m, n - j * i) * power(m - k, j)) % M;
int cur2 = (1ll * cur1 * power(k, j * (i - 1))) % M;
int cur3 = (1ll * cur2 * cnk(n - j * (i - 1) - 1, j)) % M;
if(j & 1){
if((ans += cur3) >= M){
ans -= M;
}
} else{
if((ans -= cur3) < 0){
ans += M;
}
}
}
for(int j = 0; j * i <= n - i; j++){
int cur1 = (1ll * power(m, n - (j + 1) * i + 1) * power(m - k, j)) % M;
int cur2 = (1ll * cur1 * power(k, (j + 1) * (i - 1))) % M;
int cur3 = (1ll * cur2 * cnk(n - j * (i - 1) - i, j)) % M;
if(j & 1){
if((ans -= cur3) < 0){
ans += M;
}
} else{
if((ans += cur3) >= M){
ans -= M;
}
}
}
}
cout << (1ll * ans * inv(power(m, n))) % M << endl;
return 0;
}