NotImplemented's blog

Can anybody give hints on how to approach SRM 581 Div-1 Medium?
By NotImplemented, 11 years ago, In Russian

SRM 581 Div-1 Medium

  • Vote: I like it
  • -13
  • Vote: I do not like it

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

The point is that k <= 7. So it easy to proof that there would be exactly 2 edges between different trees in any cycle. Now we just need to calc d[x] — how many path of lenth x there are in both trees and the answer would be summ (x = 1 .. K — 3) 2 * d1[x] * d2[k — 2 — x] / n / (n — 1).

→ Reply