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?