electro177's blog

By electro177, history, 3 years ago, In English

Hello codeforces,hope we all are doing well:)i have some doubts in some question which came in my coding test

1)Given a undirected tree,you are at the root node .some of the nodes have cake in them and you takes one secong to walk over one edge.find the minimum time to catch all the cakes and come back to the stating node(root node in which you were standing at time=0) (i thought it might be dfs but do not know how to come up with it)

constraints:N<=1e4;(no of nodes)

2)About modulo for large number: p=2^(100)-1 and q=2^(1000001)-1 how to find p*inverse(q),where inverse(q) is the inverse modulo of q with 10^9+7.I have no clue bec for smaller number we could do iterative thing

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

To solve problem 1), you can dfs from the root, and get all the nodes that don't have children with cake. Than the answer is 2*lenght of each one (you go down and then back, for each one).

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

maybe you can use Fermat theorem. x^(p-1)=1 mod p. so modular inverse of x is x^(p-2). you can find q mod 1e9+7 and then calculate its modular inverse using this formula.