Solution of 1785D (a typical FFT problem)

Правка en4, от YocyCraft, 2023-02-07 08:03:43

First, WLOG we can assume we arrange the tournament in such way: In the every match, the left player wins. We can achieve this by doing the following operation to the binary tree of the tournament: for each non-leaf node of the binary tree, if the winner of this node is its right child, swap its left subtree and right subtree. Since fliping doesn't change the winner of each match, this will not change the "wooden spoon", and after this operation, the "wooden spoon" is the right-most node. Since there are 2^n-1 nodes in the binary tree, we can merge 2^(2^n-1) situations into one by this operation.

For example, we can do operation to this tree:

_________1

_____3_______1

-__5___3___1___2

__7 5 3 6 1 8 4 2

-->

_________1

_____1_______3

-__1___2___3___5

__1 8 2 4 3 6 5 7

Where 1 (the left-most node) is the champion, and 7 (the right-most node) is the "wooden spoon".

Then we assume the right-most node is k, and there's dp[n][k] different arrangements (after operation). If k is the j-th smallest element in the right half of the tree, then we have sum(i=1...2^(n-1))(dp[n-1][i]) ways to arrange the left half, and dp[n-1][j] ways to arrange the right half (since k is also the right-most node in the right-subtree). But in how many ways we can distribute 2^n elements into 2 halves? Well, since 1 is the left-most element, there are k-2 elements we could put in the right part (which are in the range [2, k-1]), and there are actually j-1 elements of them in the right part, so we have C(k-2,j-1) ways to choose them. Similarly, we have C(2^n-k, 2^(n-1)-j) ways to choose elements from [k+1, 2^k]. Therefore, we can get such formula:

dp[n][k]=sum(i=1...2^(n-1))(dp[n-1][i])*dp[n-1][j]*C(k-2,j-1)*C(2^n-k,2^(n-1)-j)

Then we can calculate them by FFT. The answer is 2^(2^n-1)*dp[n][k].

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en13 Английский YocyCraft 2023-02-07 13:51:13 28
en12 Английский YocyCraft 2023-02-07 13:49:21 1 Tiny change: '{2^{n-1}}(sum_{i=1}^' -> '{2^{n-1}}(\sum_{i=1}^'
en11 Английский YocyCraft 2023-02-07 13:48:50 210 Tiny change: 'can merge 2^(2^n-1) situation' -> 'can merge $$2^{2^n-1} situation'
en10 Английский YocyCraft 2023-02-07 12:48:19 20
en9 Английский YocyCraft 2023-02-07 08:15:54 6
en8 Английский YocyCraft 2023-02-07 08:14:03 6 Tiny change: 'h way: In the every match, the left' -> 'h way: In every matches, the left'
en7 Английский YocyCraft 2023-02-07 08:08:59 29 Tiny change: 'ht child, swap its left ' -> 'ht child, we "flip" this node by swapping its left '
en6 Английский YocyCraft 2023-02-07 08:05:49 6715
en5 Английский YocyCraft 2023-02-07 08:04:17 28
en4 Английский YocyCraft 2023-02-07 08:03:43 4
en3 Английский YocyCraft 2023-02-07 08:03:24 64
en2 Английский YocyCraft 2023-02-07 08:02:39 76
en1 Английский YocyCraft 2023-02-07 08:01:52 1884 Initial revision (published)