今天做到一个题，就是 $q$ 次询问从 $(0,0)$ 到 $(x,y)$ ，每次可以走上下左右，总共 $k$ 步的方案数。

$q,k,x,y\le 10^6$

其实就是可以考虑暴力做法，设左边的有 $a$ 步，右边 $b$ 步，上 $c$ 步，下 $d$ 步，那么有：

$b-a=x,d-c=y$。

然后剩下的 $k$ 步可以任意投放在 $(a,b)$ 或 $(c,d)$ 中，个数确定之后，求排列组合本质不同方案数就行了，因此答案就为：

令 $t=\dfrac{k-x-y}{2}$，$ans=k!\sum\limits_{i=0}^t\dfrac{1}{i!(t-i)!}\dfrac{1}{(x+i)!(y+t-i)!}$。

显然过不去。

但是答案用了一种很巧妙的方法，就是把坐标轴旋转四十五度，然后乘 $\sqrt 2$ 倍，那么横纵坐标就相互独立了，答案就为：

旋转后坐标为 $(nx,ny)$，$ans=\dbinom{\frac{k-nx}{2}}{k}\dbinom{\frac{k-ny}{2}}{k}$

那么问题来了：为什么这个相同呢？

从组合意义上是这样的，问题是做题的时候想不到，因此想要数学证明。

简而意之，求证：

$k!\sum\limits_{i=0}^t \dfrac{1}{i!(\frac{k-x-y}{2}-i)!}\dfrac{1}{(x+i)!(y+\frac{k-x-y}{2}-i)!}=\dbinom{\frac{k-nx}{2}}{k}\dbinom{\frac{k-ny}{2}}{k}$

萌新数学很菜，望会的大佬给出详细的证明，too_late 不尽感激。