Contest Duration: - (local time) (100 minutes) Back to Home

## G - Teleporting Takahashi Editorial by LHF

English Editorial:

Without loss of generality, we can only consider the case $$x,y,z\ge 0$$.

First, let’s solve the case that the answer is $$0$$.

If $$x+y+z>n$$ or $$(n-x-y-z)\bmod 2=1$$, than the answer is $$0$$.

Consider the other case in a two-dimensional plane.

Let $$F[k]$$ denote a scheme that takes $$x+y+2k$$ steps from $$(0,0)$$ to $$(x,y)$$.

We have

\begin{aligned} F[k]&=\sum_{i=0}^k\binom {x+y+2k}{x+i\;\;i\;\;y+k-i\;\;k-i}\\ &=\sum_{i=0}^k\binom{x+y+2k}{x+y+k}\binom{x+y+k}{y+k-i}\binom{k}{i}\\ &=\binom{x+y+2k}{x+y+k}\sum_{i=0}^k\binom{x+y+k}{y+k-i}\binom{k}{i}\\ &=\binom{x+y+2k}{x+y+k}\binom{x+y+2k}{y+k} \end{aligned}

The last step is equivalent to the number of solutions that have $$x+y+2k$$ balls and put them into $$y+k$$ boxes. Specifically, we can enumerate how many balls are placed in the last $$k$$ box.

And we can insert the third dimension, we can use insertion method to solve it.

\begin{aligned} F[k]&=\sum_{i=0}^k\binom {x+y+2k}{x+i\;\;i\;\;y+k-i\;\;k-i}\\ &=\sum_{i=0}^k\binom{x+y+2k}{x+y+k}\binom{x+y+k}{y+k-i}\binom{k}{i}\\ &=\binom{x+y+2k}{x+y+k}\sum_{i=0}^k\binom{x+y+k}{y+k-i}\binom{k}{i}\\ &=\binom{x+y+2k}{x+y+k}\binom{x+y+2k}{y+k} \end{aligned}

posted:
last update: