Total number of matchings in complete bipartite graph with fixed sizes of parts

Правка ru1, от La_Pushok, 2020-06-20 09:35:08

As a backstory: I was solving a past atcoder problem, found some cubic DP-solution (different from the editorial one) being something like "$$$dp[v][x]$$$ — we have $$$X$$$ non-matched vertices in $$$V$$$'s subtree, its child $$$TO$$$ has $$$Y$$$ ones, we want to choose some $$$Z$$$ of $$$X$$$ and $$$Z$$$ of $$$Y$$$ to match them and update". However, that's too slow to get accepted.

Thus, the solution can be optimized if, for example, we can precalculate some $$$VAL[x][y]$$$, meaning number of matchings (**not necessarily maximum ones**) in a complete bipartite graph having left part of size $$$X$$$ and right part of size $$$Y$$$, faster that $$$N^3$$$. The obvious formula would be to fix $$$Z$$$ nodes we match and count the $$$VAL[x][y]$$$ through $$$C(n, k)$$$ which I have not been capable neither to find any paper related to it on the Internet nor to get to any observation.

Are there any kind of resources to seek at, or, perhaps, some ideas on getting the precalcution in time?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru2 Русский La_Pushok 2020-06-20 15:54:31 5 Мелкая правка: 'servation.\n\nAre there ' -> 'servation. Are there '
en1 Английский La_Pushok 2020-06-20 09:37:53 1077 Initial revision for English translation
ru1 Русский La_Pushok 2020-06-20 09:35:08 1075 Первая редакция (опубликовано)