Challenge: Robanukkah Tree
Subdomeniu: Combinatorics (combinatorics)
Scor cont: 90.0 / 90
Submission status: Accepted
Submission score: 1.0
Submission ID: 464808448
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/r-tree-decoration/problem
Cerinta
Robot Bender is celebrating Robanukkah, the most important holiday for robots.
He <s>stole</s> bought a Robanukkah tree, which is actually a common tree (i.e., a connected acyclic graph with $N$ vertices). He wants to decorate it with regular [polyhedrons](https://en.wikipedia.org/wiki/Polyhedron) by placing one regular polyhedron in each vertex.
A regular polyhedron is a convex polyhedron whose faces are identical regular polygons. There are five types of regular polyhedrons:
<img src="https://s3.amazonaws.com/hr-challenge-images/15554/1469365303-23972b13c3-hedron.jpg" title="hedron.jpg" />
Bender has $F$ types of polyhedrons. All polyhedrons of the same type are indistinguishable by their shape. Bender has at least $N$ polyhedrons of each available type.
In addition, Bender has $K$ colors. He paints each face of each polyhedron in *one* of these colors.
Bender considers two polyhedrons to be _similar_ if one of the following is true:
* They are of the same type.
* Some face of the first polyhedron and some face of the second polyhedron are painted with the same color.
Bender considers the decorated tree to be _beautiful_ if any two adjacent vertices don't contain similar polyhedrons. In particular, any decoration of a one-vertex tree is beautiful.
Two polyhedrons are equally painted if it is possible to rotate and move one of them so that it coincides with the other *and* the coincided faces are painted in the same color.
Two decorations of the tree are the same if each vertex in both decorations has equally painted polyhedrons.
Can you help Bender find the number of ways he can decorate his tree beautifully? Find and print it modulo $10^9+9$.Input Format
The first line contains three space-separated integers denoting the respective values of $N$ (the number of vertices in the tree), $K$ (the number of available colors), and $F$ (the number of types of polyhedrons).
The second line contains $F$ different space-separated numbers describing $f_1, \dots, f_F$, where $f_i$ is the number of faces of polyhedrons of the $i^{th}$ type. $f_i \in \{4,6,8,12,20\}$.
The third line contains $N-1$ space-separated numbers describing $p_2, \dots, p_N$, where $p_i$ is index of parent of $i^{th}$ vertex. The root of the tree has index $1$.
**Note:** If the tree consists of only one vertex, the third line will be empty.Output Format
Print a single integer denoting the number of ways to decorate the tree modulo $10^9+9$.Constraints
* $1 \le N \le 5 \times 10^4$
* $1 \le K \le 10^5$
* $1 \le F \le 5$Cod sursa
#include <bits/stdc++.h>
using namespace std;
static constexpr int MOD = 1000000009;
static inline int addmod(int a, int b) {
int s = a + b;
if (s >= MOD) s -= MOD;
if (s < 0) s += MOD;
return s;
}
static inline int mulmod(long long a, long long b) {
return int((a * b) % MOD);
}
static int mod_pow(long long a, long long e) {
long long r = 1 % MOD;
a %= MOD;
while (e > 0) {
if (e & 1) r = (r * a) % MOD;
a = (a * a) % MOD;
e >>= 1;
}
return int(r);
}
static int mod_inv(int a) { return mod_pow(a, MOD - 2); }
static int burnside(int faces, int c) {
const int inv12 = mod_inv(12);
const int inv24 = mod_inv(24);
const int inv60 = mod_inv(60);
auto P = [&](int k) -> int { return mod_pow(c, k); };
if (faces == 4) {
int res = addmod(P(4), mulmod(11, P(2)));
return mulmod(res, inv12);
}
if (faces == 6) {
long long res = 0;
res = (res + P(6)) % MOD;
res = (res + 3LL * P(4)) % MOD;
res = (res + 12LL * P(3)) % MOD;
res = (res + 8LL * P(2)) % MOD;
return mulmod(res, inv24);
}
if (faces == 8) {
long long res = 0;
res = (res + P(8)) % MOD;
res = (res + 17LL * P(4)) % MOD;
res = (res + 6LL * P(2)) % MOD;
return mulmod(res, inv24);
}
if (faces == 12) {
long long res = 0;
res = (res + P(12)) % MOD;
res = (res + 44LL * P(4)) % MOD;
res = (res + 15LL * P(6)) % MOD;
return mulmod(res, inv60);
}
if (faces == 20) {
long long res = 0;
res = (res + P(20)) % MOD;
res = (res + 15LL * P(10)) % MOD;
res = (res + 20LL * P(8)) % MOD;
res = (res + 24LL * P(4)) % MOD;
return mulmod(res, inv60);
}
return 0;
}
static inline int Cnk(int n, int k, const vector<int>& fact, const vector<int>& ifact) {
if (k < 0 || k > n) return 0;
return mulmod(fact[n], mulmod(ifact[k], ifact[n - k]));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, nc, nf;
cin >> n >> nc >> nf;
vector<int> faces(nf);
int maxFaces = 0;
for (int i = 0; i < nf; i++) {
cin >> faces[i];
maxFaces = max(maxFaces, faces[i]);
}
vector<vector<int>> children(n);
if (n >= 2) {
for (int v = 2; v <= n; v++) {
int p;
cin >> p;
--p;
children[p].push_back(v - 1);
}
}
vector<int> fact(nc + 1), ifact(nc + 1);
fact[0] = 1;
for (int i = 1; i <= nc; i++) fact[i] = mulmod(fact[i - 1], i);
ifact[nc] = mod_inv(fact[nc]);
for (int i = nc; i >= 1; i--) ifact[i - 1] = mulmod(ifact[i], i);
vector<vector<int>> exact(nf, vector<int>(maxFaces + 1, 0));
for (int t = 0; t < nf; t++) {
int F = faces[t];
vector<int> total(F + 1, 0);
for (int q = 1; q <= F; q++) total[q] = burnside(F, q);
for (int q = 1; q <= F; q++) {
long long val = total[q];
for (int l = 1; l < q; l++) {
val = (val - 1LL * Cnk(q, l, fact, ifact) * exact[t][l]) % MOD;
}
if (val < 0) val += MOD;
exact[t][q] = (int)val;
}
}
vector<vector<vector<int>>> trans(maxFaces + 1,
vector<vector<int>>(nf, vector<int>(maxFaces + 1, 0)));
for (int pu = 0; pu <= maxFaces; pu++) {
for (int t = 0; t < nf; t++) {
for (int q = 1; q <= faces[t]; q++) {
trans[pu][t][q] = (nc - pu >= q) ? mulmod(Cnk(nc - pu, q, fact, ifact), exact[t][q]) : 0;
}
}
}
vector<int> order;
order.reserve(n);
{
vector<int> st;
st.push_back(0);
while (!st.empty()) {
int u = st.back();
st.pop_back();
order.push_back(u);
for (int v : children[u]) st.push_back(v);
}
}
const int Q = maxFaces + 1;
auto idx = [&](int u, int t, int q) -> size_t {
return (size_t)(u * nf + t) * Q + q;
};
vector<int> dp((size_t)n * nf * Q, 0);
for (int u = 0; u < n; u++) {
for (int t = 0; t < nf; t++) {
for (int q = 1; q <= faces[t]; q++) dp[idx(u, t, q)] = 1;
}
}
vector<int> sumAll(maxFaces + 1);
vector<vector<int>> sumSame(nf, vector<int>(maxFaces + 1));
for (int it = (int)order.size() - 1; it >= 0; it--) {
int u = order[it];
for (int v : children[u]) {
fill(sumAll.begin(), sumAll.end(), 0);
for (int t = 0; t < nf; t++) fill(sumSame[t].begin(), sumSame[t].end(), 0);
for (int tc = 0; tc < nf; tc++) {
for (int qc = 1; qc <= faces[tc]; qc++) {
int waysSub = dp[idx(v, tc, qc)];
if (!waysSub) continue;
for (int pu = 0; pu <= maxFaces; pu++) {
int waysColors = trans[pu][tc][qc];
if (!waysColors) continue;
int contrib = mulmod(waysSub, waysColors);
sumAll[pu] = addmod(sumAll[pu], contrib);
sumSame[tc][pu] = addmod(sumSame[tc][pu], contrib);
}
}
}
for (int tp = 0; tp < nf; tp++) {
for (int qu = 1; qu <= faces[tp]; qu++) {
int waysChild = addmod(sumAll[qu], -sumSame[tp][qu]);
dp[idx(u, tp, qu)] = mulmod(dp[idx(u, tp, qu)], waysChild);
}
}
}
}
long long ans = 0;
for (int t = 0; t < nf; t++) {
for (int q = 1; q <= faces[t]; q++) {
ans += 1LL * dp[idx(0, t, q)] * trans[0][t][q];
ans %= MOD;
}
}
cout << (int)ans << "\n";
return 0;
}
HackerRank Combinatorics – Robanukkah Tree