Блог пользователя pimenta

Автор pimenta, 9 лет назад, По-английски

Hi,

I'm trying to solve this problem, which asks the number of labeled trees with N vertices and maximum degree K (modulo 109 + 7), where 1 ≤ N ≤ 100 and 1 ≤ K ≤ N.

What I have so far:

If f(n, k) is the answer, then f(n, k) = f(n, k - 1) + g(n, k), where g(n, k) is the number of labeled trees with n vertices, at least one vertex with degree k and no vertex with degree larger than k. But, is there a formula for g(n, k)?

f(n, 2) = n! / 2, because this is the case of a "list" tree. The answer is the number of permutations (n!), removing duplicates ( / 2), such as 1<->2<->3 and 3<->2<->1 (for f(3, 2)).

And, of course, f(n, 1) = 0, f(1, k) = 1, f(2, k) = 1 and f(n, n) = f(n, n - 1).

There is also Cayley's formula: the number of labeled trees with n vertices is nn - 2. Then f(n, n - 1) = nn - 2.

Thanks in advance for any help!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by pimenta (previous revision, new revision, compare).

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

http://mirror.codeforces.com/blog/entry/20335

There are at least 4 solutions there, including one which works in O(nlog2n) (apparently for any modulo, as I've just learned. How did I miss that post 5 weeks ago?)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks!

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Well, actually it's easy for the generating polynomial exponentiation to work with 10^9+7.

    Just use Number Theoretic Transform with Chinese remainder theorem. Just compute it for 2 primes of form 2^b+1 (where b<60 is the desired bits in maximum of N). You will have to use __int128 in c++ or BigInteger in Java though for the last few computations. See the codeforce discussion here.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

There is bijection between labeled trees and Prufer sequences. Every vertex v contains in sequence exactly degreev - 1 times. That means you should calculate number f(K) of sequences of numbers from 1 to n having length n - 2, such that every number contains at most K - 1 times. It can be done with some combinatorics or dynamic programming.