PROBLEM LINK
Panel Members
Problem Setter: Sergey Nagin
Problem Tester: Istvan Nagy
Editorialist: Sunny Aggarwal
Contest Admin: Praveen Dhinwa
Russian Translator: Sergey Nagin
Mandarin Translator: Hu Zecong
Vietnamese Translator: VNOI Team
Language Verifier: Rahul Arora
DIFFICULTY:
medium
PREREQUISITES:
Dynamic Programming, Number Theory, Trees
PROBLEM:
Given a rooted tree T consisting of N nodes and an integer M. We are asked to calculate the number of ways of putting integers from range [1, M] in each node of the tree T such that for any pair of nodes \left(A, B\right) ( where A is parent of node B ) the number assigned to node B is divisible by the number assigned to node A. Since this answer can be very large, Print the answer modulo 10^9 + 7.
QUICK EXPLANATION
Number of valid configuration (as mentioned in problem statement) for a tree rooted at a node can be computed from the valid configuration of trees rooted at its children nodes i.e number of ways of assigning a particular number say K to a node say V such that the tree rooted at node V has a valid configuration can be calculated from the number of ways of assigning multiples of number K to the children nodes of V such that trees rooted at children nodes also has a valid configuration.
EXPLANATION
Lets use some notation to make the explanation more understandable. Let us consider that the function F_{\left(V, K\right)} denotes the number of ways of assigning a number K to the node V such that tree rooted at node V has a valid configuration and the function D_{\left(V, K\right)} denotes the number of ways of assigning any multiple of number K to the node V such that tree rooted at node V has a valid configuration.
Therefore,
How to compute F_{(V, K)} for all K \in [1, M] for any node V ?
As mentioned above, number of ways of assigning a particular number say K to a node say V such that the tree rooted at node V has a valid configuration can be calculated from the number of ways of assigning multiples of number K to the children nodes of V such that trees rooted at children nodes also has a valid configuration.
For any non leaf node V,
otherwise
Note that the function F for a node V depends upon the children nodes of V.
How to compute D_{(V, K)} for all K \in [1, M] for any node V ?
Let us consider that we have already calculated F_{(V, K)} for all K \in [1, M].
Then, For some K \in [1, M]
Note that the function D for a node V depends upon the function F for the same node V and can be computed using following simple procedure.
int D[M+1];
int F[M+1];
for(int i=1; i<=M; i++) {
int j = i;
while( j<=M ) { // iterating over multiples of i
D[i] += F[j];
j += i;
}
}
Look at the following C++ code for the better understanding of above explanation:
int N, M;
int F[N+1][M+1];
int D[N+1][M+1];
void dfs(int u, int p = -1) {
bool isleaf = true;
for(int i=1; i<adj[u].size(); i++) {
if( adj[u][i] != p ) {
isleaf = false;
dfs(adj[u][i], u);
}
}
if( isleaf ) {
// leaf node base case
for(int i=1; i<=m; i++) {
F[u][i] = 1;
}
} else {
// computing function F as per our recurrence
for(int j=1; j<=m; j++) {
int v = 1;
for(int i=0; i<adj[u].size(); i++) {
if(adj[u][i] != p) {
v = 1LL * v * D[adj[u][i]][j];
}
}
F[u][j] = v;
}
}
// computing function D using function F.
for(int i=1; i<=m; i++) {
int j = i;
while( j <= m ) {
D[u][i] += F[u][j];
j += i;
}
}
}
COMPLEXITY
O(NM\log(M)) per test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
The author’s solution can be found here.
The tester’s solution can be found here.
The editorialist’s solution can be found here.
SIMILAR PROBLEMS:
Codeforces Testing round 10 - D
