Nan_Hao's blog

By Nan_Hao, history, 4 weeks ago, In English

In the problem k-tree on codeforces, i tried the following approach but it doesn’t seem to work, can someone please take a look at it and tell me where I’m wrong? My Approach: We’re asked to calculate the number of paths starting from the root have a total weight n, with a slight twist that each path must consist of at least one edge with weight at least d. So what i thought is that I essentially need to calculate all the paths starting from the root having the required weight(without any restrictions), and subtract from it the number of paths where no edge has a weight greater than or equal to k. the function formulation was as follows: let f(sum,k) be the paths from root with weight equal to sum and the maximum weight that any edge can have as k, then the required answer should be: f(n,k)-f(n,d-1) where n is the weight required, k is the maximum weight of any edge and d is the weight, such that at least one edge with weight greater than or equal to this must be present. I’ve checked the code several times and couldn’t find any deviation in it from my thinking so I wondered if you guys could help me figure out what’s wrong with my approach. Thanks.``

  • Vote: I like it
  • 0
  • Vote: I do not like it

4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

You can look what you output, you definitely have an overflow.

You know, you can't just write (x - y) % mod, it has to be (x - y + mod) % mod.

C++ doesn't work mathematically correctly with negative modulo.