codeingerman's blog

By codeingerman, 6 days ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
6 days ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain the later part? You need to maintain all the gcd equal to 1.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Yeah, M is small. Sorry about the mistake. Have updated it.

      • »
        »
        »
        »
        46 hours ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Can you please give some more brief on recurrence relation for solving this subproblem.

»
6 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Change the constraint on M, it was $$$1 \leq M \leq 20$$$