A tree is given having N nodes numbered from 1 to N, rooted at 1. We are also given a positive integer M, the value of each node can be anything from 1 to M.
Let's say a tree is beautiful if there is at least one leaf node such that gcd of values of each node on the path from that leaf node to the root node is greater than 1.
Now, we need to calculate the number of ways in which we can assign values to all the nodes such that we get a beautiful tree. Two ways are different if there is at least one node having different values. We are supposed to return the answer modulo 1e9 + 7.
Constraints:
- 1 ≤ N ≤ 1e5
- 1 ≤ M ≤ 20
Note: This problem is not from any running contest, it was asked in the campus placement test.
Hint: Change "at least one" to "all possible way" minus "none". Number of tree with atleast one such leaf is same as total number of trees minus number of trees that has no such leaf. The later one is easier to calculate.
Could you please explain the later part? You need to maintain all the gcd equal to 1.
If $$$M$$$ is small, then you can do dp[node][gcd from node to root] = number of ways to fill the subtree of this node.
Yeah, M is small. Sorry about the mistake. Have updated it.
Change the constraint on M, it was $$$1 \leq M \leq 20$$$