Consider a suit that's not the trump suit (not suit 1). How many ways can we distribute $$$x$$$ cards to $$$A$$$ (and thus $$$m-x$$$ cards to $$$B$$$)?
- If we receive more cards than them ($$$x \gt m-x$$$), then we're screwed, because after we beat all of their cards we will have some non-trump-suit cards left over which can't beat anything, so we don't win.
- If we receive less or equal cards than them, assume we can use all of our cards to beat some of theirs, and then we'll have to use trump cards to beat the rest.
- We have to be able to use our $$$x$$$ cards to beat $$$x$$$ of their cards, otherwise we result in the situation in the first case where we have leftovers that can't beat anything.
So, in order to calculate this we can run DP:
- $$$dp[k][i]$$$ = how many ways to give ourselves $$$i$$$ cards, out of the first $$$k$$$ cards.
- Step 1: Start with card 1. We have to give it to $$$B$$$. So $$$dp[1][0] = 1$$$.
- Step $$$k$$$: Then for a card with value $$$k$$$:
- We could give it to ourselves, but not if it "overflows". So add transition from $$$dp[k-1][i]$$$ where $$$i \lt k/2$$$, $$$dp[k][i+1] += dp[k-1][i]$$$. If $$$i \gt = k/2$$$, then giving the card to ourselves results in it being left over.
- Or we give it to our opponents. So transition $$$dp[k][i] += dp[k-1][i]$$$.
- By processing the cards from smallest to greatest, the current card is guaranteed to beat all previous cards.
This DP takes $$$O(m^2)$$$ since $$$k$$$ and $$$i$$$ both go up to $$$m$$$.
Okay, now we want another DP to know how many ways to give us cards out of suits $$$2...n$$$.
- $$$dp2[k][i]$$$ = how many ways to give us $$$i$$$ cards, out of the suits $$$2...k$$$.
- We start with suit $$$k=2$$$ and base case $$$dp2[1][0] = 1$$$.
- For each $$$dp2[k-1][i]$$$, we can give ourselves $$$j$$$ cards (to then have $$$i+j$$$ cards total), and there are $$$dp[m][j]$$$ ways to do that. So we do $$$dp2[k][i+j] += dp[m][j] \cdot dp2[k-1][i]$$$ (and reduce modulo if needed). (We have to do this for each value of $$$j$$$ from $$$1$$$ to $$$m/2$$$.)
- Repeat for each future suit.
There are $$$n^2 m$$$ states in $$$dp2$$$ (note that $$$i$$$ goes up to $$$n m$$$), and the transition takes $$$m$$$ time, for $$$n^2 m^2$$$ total. That's going to TLE.
Let's remind ourselves what we care about. If we get $$$i$$$ cards from the non-trump suit, then we need to have $$$\frac{nm}{2} - i$$$ more trump cards than our opponent. And since we can have no more than $$$m$$$ more trump cards than our opponent, we really only care about having between $$$\frac{nm}{2} - m$$$ and $$$\frac{nm}{2}$$$ cards $$$i$$$.
So at step $$$k$$$ in $$$dp2$$$, we only really care about the values of $$$i$$$ in the range $$$\frac{m}{2}k-m$$$ to $$$\frac{m}{2}k$$$. That's because you can only add $$$\frac{m}{2}$$$ elements per step, so if you're below $$$\frac{m}{2}k - m$$$, you are irrelevant to the final answer. So now we really only have $$$m$$$ states, and we run in $$$O(n m^2)$$$ and don't TLE anymore. Yay!
Extra note: To extract the answer, you sum together all the results of multiplying $$$dp2[n][i]$$$ by the number of ways to have $$$\frac{nm}{2} - i$$$ more trump cards than our opponent. To calculate this, it's very similar to DP before, but this time start from the highest trump card (which has to be ours), then work your way down. At every point, you should have equal or more trump cards than your opponent.
