超几何函数和其他函数

超几何变换

先来看一些封闭形式，比如和式 $\displaystyle \sum_{k \leqslant m} \binom{n}{k}$ 对应于

$\displaystyle \binom{n}{m} F\left(\begin{gathered} 1, -m \\ n-m+1 \end{gathered} \middle| \ -1\right), \quad n \geqslant m \geqslant 0$

将上式进行化简，等价于 $\displaystyle \binom{n}{m} \sum_k \frac{ \binom{m}{k} }{ \binom{n-m+k}{k} } = \sum_k \frac{n!}{m!(n-m)!} \cdot \frac{m!(n-m)!}{(m-k)!(n-m+k)!}$

进一步化简， $\displaystyle \sum_k \binom{n}{m-k} = \sum_{k'\leqslant m} \binom{n}{k'}$，证明完毕

反射定律

$\displaystyle \frac{1}{(1-z)^a} F\left(\begin{gathered} a, b \\ c \end{gathered} \middle| \ \frac{-z}{1-z}\right) = F\left(\begin{gathered} a, c-b \\ c \end{gathered} \middle| \ z \right)$

根据二项展开，不难写出左边等于

$\displaystyle \sum_{k \geqslant 0}\frac{a^{\overline{k}} b^{\overline{k}}}{c^{\overline{k}}} \cdot \frac{(-z)^k}{k!} \cdot \sum_{m \geqslant 0} \binom{k+a+m-1}{m}z^m$
令 $k+m = n$，求和可以写成，$\displaystyle \sum_{n \geqslant 0} z^n \sum_{k \geqslant 0} \frac{a^{\overline{k}} b^{\overline{k}}}{c^{\overline{k}} k!} (-1)^k \binom{n+a-1}{n-k}$
对 $z^n$ 的系数展开
$\displaystyle \frac{(a-1)!a(a+1)\cdots (a+k-1) \cdot b(b+1)\cdots (b+k-1)}{(a-1)!c(c+1)\cdots (c+k-1) \cdot k!} \cdot (-1)^k \frac{(n+a-1)!}{(n-k)! (a+k-1)!}$
$(a+k-1)!$ 可以约去，将 $(-1)^k$ 开始的后半部分做一个变形

$\displaystyle (-1)^k \frac{(n+a-1)! \cdot (n-k+1)(n-k+2) \cdots n}{(n-k)! (n-k+1)(n-k+2)\cdots n}$
综上所述，可以将原式化简成
$\displaystyle \frac{b^{\overline{k}} }{c^{\overline{k}} k!} \cdot \frac{(n+a-1)! \cdot (-n)^{\overline{k}}}{n! (a-1)!} = \binom{n+a-1}{n} F\left(\begin{gathered} a, b, -n \\ c, a \end{gathered} \middle| \ 1 \right)$

根据范德蒙卷积，多项式的超几何表示这一节内容的 $\textbf{(3)}$，原式为 $\displaystyle \frac{a^{\overline{n}}}{n!} \frac{(c-b)^{\overline{n}}}{c^{\overline{n}}}$

库默尔公式和反射定律

令 $c = 1+b-a$ 代入反射定律中，可以得到

$\displaystyle 2^{-a} F\left(\begin{gathered} a, 1-a \\ 1+b-a \end{gathered} \middle| \ \frac{1}{2}\right) = F\left(\begin{gathered} a, b \\ 1+b-a \end{gathered} \middle| \ -1 \right) = \frac{(b/2)!}{b!} (b-a)^{\underline{b/2}}$

令 $a= -n$ 就可以得到一个新的恒等式

$\displaystyle \sum_{k\geqslant 0} \frac{(-n)^{\overline{k}} (1+n)^{\overline{k}} }{(1+b+n)^{\overline{k}}} \frac{2^{-k}}{k!} = \sum_k \binom{n}{k} \left(\frac{-1}{2} \right)^k \binom{n+k}{k}\bigg / \binom{n+b+k}{k}$

$\displaystyle \quad \quad = 2^{-n}\frac{(b/2)!(b+n)!}{b!(b/2+n)!}$

其他一些恒等式

$\displaystyle \sum_{k \leqslant m} \binom{m+k}{k}2^{-k} = 2^m$，令 $k' = m - k$ 代入，可以得到

$\displaystyle \sum_{k \geqslant 0} \binom{2m-k}{m-k}2^k = 2^m$，写成超几何形式，令 $\displaystyle \frac{t_{k+1}}{t_k} = \frac{2(k-m)(k+1)}{(k-2m)(k+1)}$

$\displaystyle \binom{2m}{m} F\left(\begin{gathered} 1, -m \\ -2m \end{gathered} \middle| \ 2\right) = 2^{2m}$

但这个形式并不是标准形式，因为下参数 $-2m$ 被禁止的

但 $\displaystyle \binom{2m}{m} F\left(\begin{gathered} 1, -m \\ -2m \end{gathered} \middle| \ 2\right) = 2^{2m}$ 表示 $\displaystyle \sum_{k \geqslant 0}\binom{2m-k}{m-k} 2^k$
我们想要令 $k > m$ 的项都为 $0$（二项式下指标 $< 0$ 时值都为 $0$）

注意到上参数，$(-m)^{\overline{k}}$ 形式是 $(\cdots (-m+k-1)(-m+k) \cdots)$，在 $k > m$ 的时候，一定包含 $0$
所以对于 $k > m$ 的项，$F$ 展开分子为 $0$

为了使极限有良好定义，对超几何函数 $F$ 的下参数取极限，具体来说

$\displaystyle \binom{2m}{m} \lim_{\epsilon \to \infty} F\left(\begin{gathered} 1, -m \\ -2m+\epsilon \end{gathered} \middle| \ 2\right) = 2^{2m}, \quad m \geqslant 0$

这样，分子在 $k > m$ 时候为 $0$，分母 $(-2m)^{\overline{k}}$ 在 $k > 2m$ 时才为 $0$，这样以来，极限刚好给出了良好的定义

$\textbf{(1)}$

$\displaystyle \binom{2m}{m} \lim_{\varepsilon \to \infty} F\left(\begin{gathered} 1, -m \\ -2m+\varepsilon \end{gathered} \middle| \ 2\right) = 2^{2m}, \quad m \geqslant 0$

根据 $\textbf{(1)}$ 可以推出其他恒等式，在反射定律中，令 $z = 2, a = -m, b = 1, c = -2m + \varepsilon$

$\displaystyle (-1)^m \lim_{\varepsilon \to 0} F\left(\begin{gathered} 1, -m \\ -2m+\varepsilon \end{gathered} \middle| \ 2\right) = \lim_{\varepsilon \to 0} F\left(\begin{gathered} -m, -2m-1+\varepsilon \\ -2m+\varepsilon \end{gathered} \middle| \ 2\right)$

$\displaystyle \quad \quad = \lim_{\varepsilon \to 0} \sum_{k \geqslant 0} \frac{(-m)^{\overline{k}} (-2m-1+\varepsilon)^{\overline{k}} }{(-2m + \varepsilon)^{\overline{k}} } \cdot \frac{2^k}{k!} = \sum_{k \leqslant m} \binom{m}{k} \frac{(2m+1)^{\underline{k}}}{(2m)^{\underline{k}}} (-2)^k$

这就给出了一个公式

$\displaystyle \sum_{k \leqslant m} \binom{m}{k} \frac{2m+1}{2m+1-k}(-2)^k = (-1)^m 2^{2m} \bigg / \binom{2m}{m}$，这里用了公式 $\textbf{(1)}$
$\displaystyle \quad \quad = 1 \bigg / \binom{-1/2}{m}, \quad m \geqslant 0$

$\displaystyle (-1)^m 2^{2m} \frac{m!m!}{(2m)(2m-1)\cdots 2 \cdot 1} = (-1)^m \cdot \frac{m!m!}{m(m-\frac{1}{2}) (m - \frac{2}{2}) \cdots 1 \cdot \frac{1}{2} }$

$\displaystyle \quad \quad = \frac{m!m!}{ (m(m-1)\cdots 1) \cdot \left( (-\frac{1}{2}+m) (-\frac{3}{2}+m) \cdots (\frac{1}{2}) \right)} \cdot (-1)^m$

$\displaystyle \quad \quad = 1 \bigg / \binom{-1/2}{m}, \quad m \geqslant 0$

微分法

二项级数的部分和恒等式 描述如下

$\displaystyle \sum_{k \leqslant m} \binom{m+r}{k}x^k y^{m - k} = \sum_{k \leqslant m} \binom{-r}{k} (-x)^k (x+y)^{m-k}$

两边同时对 $y$ 微分 $n$ 次，然后令 $m-n-k$ 代替 $k$，很容易得出

$\displaystyle \sum_{k \geqslant 0} \binom{m+r}{m-n-k}\binom{n+k}{n} x^{m-n-k}y^k = \sum_{k \geqslant 0} \binom{-r}{m-n-k} \binom{n+k}{n}(-x)^{m-n-k}(x+y)^k$

展开写成超几何函数形式，左边记 $\displaystyle \frac{t_{k+1}}{t_k}$，右边记 $\displaystyle \frac{t'_{k+1}}{t'_{k}}$

左边超几何表示 $t_0 \displaystyle F\left(\begin{gathered} n-m, n+1 \\ n+r+1 \end{gathered} \middle| \ -y\right)$

右边超几何表示 $t_0' \displaystyle F\left(\begin{gathered} n-m, n+1 \\ n-m-r+1 \end{gathered} \middle| \ 1+y\right)$

这里令 $\displaystyle \begin{cases}n-m = a \\ n+1 = -n' \\ n+r+1 = c \\ n-m-r+1 = a-c-n'+1\end{cases}$

另外 $\displaystyle \frac{t_0'}{t_0} = \frac{(c-a-1+n')! \cdot (c-1)!}{(c-1+n')! \cdot (c-a-1)!}$，实际上这里做了替换

$\displaystyle \begin{cases} c-a = m+r+1 \\ r-1=c+n'-1 \end{cases}$

于是我们有 $\displaystyle \frac{t_0'}{t_0} = \frac{(c-a)^{\overline{n'}}}{c^{\overline{n'}}} = \frac{(a-c)^{\underline{n'}}}{(-c)^{\underline{n'}}}$

可以推出超几何变换

$\displaystyle F\left(\begin{gathered} a, -n \\ c \end{gathered} \middle| \ z\right) = \frac{(a-c)^{\underline{n}}}{(-c)^{\underline{n}}} F\left(\begin{gathered} a, -n \\ 1-n+a-c \end{gathered} \middle| \ 1-z\right)$

超几何级数的微分

$\displaystyle \frac{d}{dz} F\left(\begin{gathered} a_1, \cdots, a_m \\ b_1, \cdots, b_n \end{gathered} \middle| \ z\right) = \sum_{k \geqslant 1} \frac{a_1^{\overline{k}} \cdots a_m^{\overline{k}} z^{k-1} }{ b_1^{\overline{k}} \cdots b_n^{\overline{k}} (k-1)!}$

作代换，令 $k-1 = k'$，从而有

$\displaystyle \quad \quad = \sum_{k+1 \geqslant 1} \frac{a_1^{\overline{k+1}} \cdots a_m^{\overline{k+1}} z^{k} }{ b_1^{\overline{k+1}} \cdots b_n^{\overline{k+1}} (k)!} = \sum_{k \geqslant 0} \frac{a_1 (a_1+1)^{\overline{k}} \cdots a_m (a_m+1)^{\overline{k}} z^{k} }{ b_1(b_1+1)^{\overline{k}} \cdots b_n(b_n+1)^{\overline{k}} (k)!}$

$\displaystyle \quad \quad = \frac{a_1\cdots a_m}{b_1 \cdots b_n} F\left(\begin{gathered} a_1+1, \cdots, a_m+1 \\ b_1+1, \cdots, b_n+1 \end{gathered} \middle| \ z\right)$

$\displaystyle \frac{d}{dz} F\left(\begin{gathered} a_1, \cdots, a_m \\ b_1, \cdots, b_n \end{gathered} \middle| \ z\right) = \frac{a_1\cdots a_m}{b_1 \cdots b_n} F\left(\begin{gathered} a_1+1, \cdots, a_m+1 \\ b_1+1, \cdots, b_n+1 \end{gathered} \middle| \ z\right)$

微分算子

记算子 $\displaystyle \vartheta = z \frac{d}{dz}$

容易推出

$\displaystyle \frac{d}{dz} F\left(\begin{gathered} a_1, \cdots, a_m \\ b_1, \cdots, b_n \end{gathered} \middle| \ z\right) = z \sum_{k \geqslant 1} \frac{a_1^{\overline{k}} \cdots a_m^{\overline{k}} z^{k-1} }{ b_1^{\overline{k}} \cdots b_n^{\overline{k}} (k-1)!} = \sum_{k \geqslant 0} \frac{ k a_1^{\overline{k}} \cdots a_m^{\overline{k}} z^{k} }{ b_1^{\overline{k}} \cdots b_n^{\overline{k}} (k)!}$

$\displaystyle (\vartheta + a_1)F\left(\begin{gathered} a_1, \cdots, a_m \\ b_1, \cdots, b_n \end{gathered} \middle| \ z\right) = \sum_{k \geqslant 0} \frac{a_1 (a_1+1)^{\overline{k}} a_2^{\overline{k}} \cdots a_m^{\overline{k}} z^k }{b_1^{\overline{k}} \cdots b_n^{\overline{k}} k! } = a_1 \cdot F\left(\begin{gathered} a_1+1, a_2, \cdots, a_m \\ b_1, \cdots, b_n \end{gathered} \middle| \ z\right)$

$\displaystyle (\vartheta + b_1-1)F\left(\begin{gathered} a_1, \cdots, a_m \\ b_1, \cdots, b_n \end{gathered} \middle| \ z\right) = \sum_{k \geqslant 0} \frac{(k+b_1-1) a_1^{\overline{k}} a_2^{\overline{k}} \cdots a_m^{\overline{k}} z^k }{b_1^{\overline{k}} \cdots b_n^{\overline{k}} k! } = \sum_{k \geqslant 0} \frac{(b_1-1) a_1^{\overline{k}} a_2^{\overline{k}} \cdots a_m^{\overline{k}} z^k }{(b_1-1)^{\overline{k}} b_2^{\overline{k}} \cdots b_n^{\overline{k}} k! }$

$\displaystyle \quad \quad = (b_1-1) F\left(\begin{gathered} a_1, \cdots, a_m \\ b_1-1, b_2, \cdots, b_n \end{gathered} \middle| \ z\right)$

从而有超几何函数微分方程如下

$\displaystyle (\vartheta + a_1)(\vartheta + a_2) \cdots (\vartheta + a_m) F = (a_1\cdots a_m) F\left(\begin{gathered} a_1+1, \cdots, a_m+1 \\ b_1, \cdots, b_n \end{gathered} \middle| \ z\right)$

$\displaystyle (\vartheta + b_1-1) \cdots (\vartheta + b_n - 1) F = (b_1-1)\cdots (b_n-1) F\left(\begin{gathered} a_1, \cdots, a_m \\ b_1-1, \cdots, b_n-1 \end{gathered} \middle| \ z\right)$

记算子 $\displaystyle \bm{D} = \frac{d}{dz}$，从而

$\displaystyle \bm{D} (\vartheta + b_1-1) \cdots (\vartheta + b_n - 1) F = (\vartheta + a_1)(\vartheta + a_2) \cdots (\vartheta + a_m) F \quad \quad \bold{(1)}$

反过来，我们可以从微分方程回到幂级数，不妨设 $\displaystyle F(z) = \sum_{k \geqslant 0} t_kz^k$ 是满足上式子的幂级数

左边，观察 $\displaystyle [z^{k+1}]$ 系数，对于 $(\vartheta + b_n - 1)$
其系数为 $Q(z) = (k+1)t_{k+1}z^{k+1} + (b_n - 1)t_{k+1}z^{k+1} = (k+b_n) t_{k+1}z^{k+1}$

$\displaystyle \bm{D} (\vartheta + b_1-1) \cdots (\vartheta + b_n - 1) F(z) = [z^k](k+1)(k+b_1)\cdots (k+b_n) t_{k+1}$
注意这里对 $z$ 求导，自然会有 $(k+1)$ 这一项

同理，右边为 $\displaystyle [z^k](k+a_1)(k+a_2)\cdots (k+a_n) t_k$

由此 $\displaystyle \frac{t_{k+1}}{t_k} = \frac{(k+a_1)(k+a_2) \cdots (k+a_m)}{(k+b_1)\cdots (k+b_n) (k+1)}$，恰好对于超几何函数表达式

另外，更为普遍的是 $2$ 个上参数的超几何表达式

$\displaystyle z(1-z)F''(z) + (c - z(a+b+1)) F'(z) - ab F(z) = 0 \quad \textbf{(2)}$

$F(z) = \displaystyle F\left(\begin{gathered} a, b \\ c \end{gathered} \middle| \ z\right)$，根据上式，$\displaystyle \bm{D}(\vartheta + c - 1)F = (\vartheta + a)(\vartheta + b) F$

其中 $(\vartheta + c - 1)F = \displaystyle zF'(z) + (c-1)F(z)$，对其求导
左边 $F'(z) + zF''(z) + (c-1)F'(z)$，右边 $\displaystyle zF'(z) + z^2 F''(z) + bz F'(z) + az F'(z) + ab F(z)$

$\displaystyle z(1-z)F''(z) + (c - z(a+b+1)) F'(z) - ab F(z) = 0$

如果幂级数 $\displaystyle F(z) = \sum_{k \geqslant 0} t_k z^k$ 满足 $\textbf{(1)}$，那么我们可以有

$\displaystyle \frac{t_{k+1}}{t_k} = \frac{(k+a_1)\cdots (k+a_m)}{(k+b_1)\cdots (k+b_n) (k+1)}$

从而 $F(z)$ 就是 $t_0 F(a_1, \cdots, a_m; \ b_1, \cdots, b_n; \ z)$

微分法应用

算子 $\displaystyle \vartheta = z \frac{\text{d}}{dz}$，所以对于 $\bold{(1)}$ 而言

右边形式为 $\displaystyle \alpha_k z^k F^{(k)}(z)$，左边有形式 $\displaystyle \beta_k z^{k-1} F^{(k)}(z)$

所以微分方程总是可以写成

$\displaystyle z^{n-1}(\beta_n - z\alpha_n)F^{(n)}(z) + \cdots + (\beta_1 - z \alpha_1)F'(z) - \alpha_0 F(z) = 0 \quad \textbf{(3)}$

写成全 $\vartheta$ 形式，可以用 $z$ 乘以 $\textbf{(1)}$ 的两边

$\vartheta(\vartheta + b_1 - 1) \cdots (\vartheta + b_n - 1) F = z(\vartheta + a_1) \cdots (\vartheta + a_m)F$

$\vartheta = (\vartheta + 1 - 1)$ 对应超几何表达式中的 $(k+1)$，$(\vartheta + b_j - 1)$ 对应因子 $(k+b_j)$，对应到超几何函数中的 $b_j^{\overline{k}}$

右边的 $z$ 对应 $z^k$，$(\vartheta + a_j)$ 对应 $a_j^{\overline{k}}$

高斯恒等式

高斯恒等式重要的理论依据是基于 $2$ 个上参数的恒等式的超几何表达，即上式 $\textbf{(2)}$

$\displaystyle F\left(\begin{gathered} 2a, 2b \\ a+b+\frac{1}{2} \end{gathered} \middle| \ x\right) = F\left(\begin{gathered} a, b \\ a+b+\frac{1}{2} \end{gathered} \middle| \ 4t(1-t) \right)$

先来看右边，令 $x = 4t(1-t)$，那么右边形式满足微分方程

$\displaystyle x(1-x)\frac{d^2 P}{dx^2} + \left(a+b+\frac{1}{2} - (a+b+1)x \right) \frac{d P}{dx} - ab P = 0 \quad \textbf{(2)}$

作变换，令 $x = 4t(1-t)$，那么有 $\displaystyle \frac{dx}{dt} = 4-8t, \quad \frac{dt}{dx} = \frac{1}{4(1-2t)}$

$\displaystyle \frac{dP}{dx} = \frac{dP}{dt} \cdot \frac{dt}{dx} = \frac{1}{4-8t} \cdot \frac{dP}{dt}$

$\displaystyle \frac{d^2 P}{dx^2} = \frac{d}{dx} \left(\frac{1}{4-8t} \right) \cdot \frac{dP}{dt} + \frac{1}{4-8t} \cdot \frac{d}{dx} \left(\frac{dP}{dt} \right)$

$\quad \quad = \displaystyle \frac{d}{dt} \left(\frac{1}{4-8t} \right) \cdot \frac{dt}{dx} \cdot \frac{dP}{dt} + \frac{1}{(4-8t)^2} \frac{d^2 P}{dt^2}$

$\quad \quad = \displaystyle \frac{1}{16(1-2t)^2} \frac{d^2 P}{dt^2} + \frac{1}{8(1-2t)^3} \frac{dP}{dt}$

原式划归如下
$\displaystyle \frac{1}{4}t(1-t) \frac{d^2 P}{dt^2} + \frac{t(1-t)}{2(1-2t)} \frac{dP}{dt} + (a+b+\frac{1}{2})(1-4t(1-t)) \frac{1}{4(1-2t)^2} \frac{dP}{dt} - \frac{2t(1-t)}{4(1-2t)} \frac{dP}{dt} - abP = 0$

$\displaystyle t(1-t) \frac{d^2 P}{dt^2} + \left(a+b+\frac{1}{2} - (2a + 2b + 1)t \right) \frac{dP}{dt} - 4abP = 0$

将高斯恒等式左边代入 $\textbf{(2)}$，恰好和上式一致，问题证毕

超几何恒等式关于二项式系数的推论

先来看一个关于复数 $\displaystyle \frac{1}{z!}$ 的定义

$\displaystyle \frac{1}{z!} = \lim_{n \to \infty} \binom{n+z}{n} n^{-z} \quad \quad \textbf{(4)}$

证明其实很简单，因为 $\displaystyle \lim_{n \to \infty} \frac{(n+m)^{\overline{m}}}{n^m} = 1$，从而 $\displaystyle \binom{n+m}{n} \cdot \frac{m!}{n^m} = 1$

令 $m = z$，即可证明

这是为了引出阶乘加倍公式

$\displaystyle x! \left(x - \frac{1}{2}\right)! = (2x)! \left(-\frac{1}{2} \right)! \bigg/ 2^{2x} \quad \quad \textbf{(5)}$

证明并不难，在 $\textbf{(4)}$ 中分别令 $z = -1/2, \quad z = x, \quad z = x-1/2$

$\displaystyle (-1/2)! = 1 \bigg/ \binom{n-1/2}{n} \cdot n^{-1/2}$

$\displaystyle x!(x-1/2)! = \binom{n+x}{n} \cdot n^{-x} \cdot n^{-x+1/2} \cdot \binom{n+x-1/2}{n}$

从而有 $\displaystyle \frac{(-1/2)!}{x!(x - 1/2)!} = \lim_{n \to +\infty} \binom{n+x}{n} \binom{n+x-1/2}{n} \cdot n^{-2x} \bigg/ \binom{n-1/2}{n} \quad \textbf{(1.0)}$

这里我们要依据两个已知的恒等式，$\displaystyle r^{\underline{k}} \left(r- \frac{1}{2} \right)^{\underline{k}} = (2r)^{\underline{2k}} \bigg / 2^{2k} \quad (1.1)$

$\displaystyle \binom{n-\frac{1}{2}}{n} = \binom{2n}{n} \bigg/ 2^{2n} \quad (1.2)$

在 $(1.1)$ 中，令 $r = n+x, \ k = n$，可以得到 $\displaystyle \frac{(n+x)^{\underline{n}}}{n!} \cdot \frac{(n+x-1/2)^{\underline{n}}}{n!} = \frac{(2n+2x)^{\underline{2n}}}{(2n)!} \cdot \frac{(2n)!}{n!n!} \cdot 2^{-2n}$

同时 $(1.2)$ 给出 $\displaystyle \binom{n-1/2}{n} = \binom{2n}{n} \cdot 2^{-2n}$

$\textbf{(1.0)}$ 化简成 $\displaystyle \lim_{n \to \infty}\binom{2x+2n}{2n} \cdot n^{-2x}$

同时在 $\textbf{(4)}$ 中令 $z = 2x, \ n \leftarrow 2n$，综上所得，可知

$\displaystyle x!(x-\frac{1}{2})! = \frac{(-\frac{1}{2})!}{\binom{2n+2x}{2n}} \cdot n^{2x}, \quad \quad (2x)! = \frac{(2n)^{2x}}{\binom{2n+2x}{2n}}$

相乘即可得到 $\textbf{(5)}$

超几何级数与二项式还有一个推论

$\displaystyle \sum_{k \leqslant m}\binom{m-k}{n} \binom{m+n+1}{k} \left(\frac{-1}{2} \right)^k = \binom{(m+n)/2}{n} 2^{n-m} [m+n \text{是偶数}], \quad m \geqslant n \geqslant 0 \quad \textbf{(6)}$

首先不难将二项式写成超几何形式 $\displaystyle \lim_{\varepsilon \to 0}\binom{m}{n}F\left(\begin{gathered} n-m, -n-m-1+\alpha \varepsilon \\ -m + \varepsilon \end{gathered} \middle| \ \frac{1}{2} \right)$

令 $\alpha = 2$，这样可以用高斯恒等式
$\displaystyle \lim_{\varepsilon \to 0}\binom{m}{n}F\left(\begin{gathered} 2(n/2-m/2), 2(-n/2-m/2-1/2+ \varepsilon) \\ -m +\varepsilon \end{gathered} \middle| \ \frac{1}{2} \right) = \lim_{\varepsilon \to 0}\binom{m}{n}F\left(\begin{gathered} n/2-m/2, -n/2-m/2-1/2+ \varepsilon \\ -m +\varepsilon \end{gathered} \middle| \ 1 \right)$

$1)\ m+n$ 是奇数，$m+n = 2N-1$，那么 $\displaystyle F = F\left(\begin{gathered} N-m-1/2, -N + \varepsilon \\ -m +\varepsilon \end{gathered} \middle| \ 1 \right)$，只要证明 $\displaystyle \lim_{\varepsilon \to 0} F = 0$

$\quad \quad$ 根据欧拉恒等式的推广，$\displaystyle F\left(\begin{gathered} a, b \\ c \end{gathered} \middle| \ 1 \right) = \frac{\Gamma(c-a-b)\Gamma(c)}{\Gamma(c-a)\Gamma(c-b)}, \quad \mathbb{R}c \geqslant \mathbb{R}a + \mathbb{R}b$

$\quad \quad$ 此时 $\displaystyle \Gamma(c-b) = \Gamma(N-m)$，因为 $2N-2m = n-m+1 \leqslant 0$
$\quad \quad$ 所以 $N \leqslant m$，因此分母 $\Gamma(N-m) \to \infty$，从而 $F \to 0$

$2)\ m+n$ 是偶数，$n-m = -2N$，那么令 $n = m - 2N$，可以得到
$\quad \quad$ $\displaystyle \lim_{\varepsilon \to 0} F\left(\begin{gathered} -N, N-m-1/2+\varepsilon \\ -m+\varepsilon \end{gathered} \middle| \ 1 \right)$

$\quad \quad$ 而这个形式恰好符合恒等式 $\displaystyle F\left(\begin{gathered} -n, a \\ c \end{gathered} \middle| \ 1 \right) = \frac{(c-a)^{\overline{n}}}{c^{\overline{n}}}$，代入
$\quad \quad \displaystyle \lim_{\varepsilon \to 0}F = \displaystyle \frac{(N-1/2)^{\underline{N}}}{m^{\underline{N}}}$

$\quad \quad$ 此时只需要证明 $\displaystyle \binom{m}{m-2N} \frac{(N-1/2)!}{(-1/2)!} \cdot \frac{(m-N)!}{m!} = \binom{m-N}{m-2N}2^{-2N}$
$\quad \quad$ 在 $\textbf{(5)}$ 中令 $x = N$，即可证明

$\displaystyle \quad \quad \frac{(m-N)!}{(m-2N)!(N)!} \cdot \frac{N!}{(2N)!} \cdot \frac{(N-1/2)!}{(-1/2)!} = \binom{m-N}{m-2N} \cdot 2^{-2N}$

至此，超几何函数只剩下差分，机械求和法两个部分没有讨论了

q-binomial

q-binomial 定义和常用结论

定义
$\displaystyle [n]_q = \sum_{i = 0}^{n-1} q^i = \lim_{x \to q} \frac{1-x^n}{1-x}, \quad [n]!_q = \prod_{i = 1}^n [i]_q$

$\displaystyle {n \brack m}_q = \frac{[n]!_q}{[m]!_q [n-m]!_q}$

性质1

$\displaystyle {n \brack m}_1 = \binom{n}{m}$

展开可得

$\displaystyle {n \brack m}_q = \displaystyle \lim_{x \to q} \displaystyle \frac{\displaystyle \prod_{i = 1}^{n} \displaystyle\frac{1-x^i}{1-x}}{\displaystyle \prod_{i = 1}^{m} \displaystyle \frac{1-x^i}{1-x} \displaystyle \prod_{i = 1}^{n - m} \displaystyle \frac{1-x^i}{1-x} } = \displaystyle \lim_{x \to q} \displaystyle \frac{\displaystyle \prod_{i = n-m+1}^{n} \displaystyle (1-x^i)}{\displaystyle \prod_{i = 1}^{m} (1-x^i)}$

性质2

$\displaystyle {n \brack m}_q = {n \brack {n-m}}_q \quad \textbf{(1)}$

若 $n \geqslant 1$，那么有

$\displaystyle {n \brack m}_q = {n-1 \brack{m-1}}_q + q^m {n-1 \brack m}_q \quad \textbf{(2)}$

证明，只需要展开即可验证
$\displaystyle {n-1 \brack{m-1}}_q + q^m {n-1 \brack m}_q$

$\quad \quad \displaystyle = \displaystyle \frac{\displaystyle \prod_{i = n-m+1}(1-q^i)}{\displaystyle \prod_{i = 1}^{m-1} (1-q^i)} + q^m \cdot \displaystyle \frac{\displaystyle \prod_{i = n-m}^{n-1} (1-q^i) }{\displaystyle \prod_{i = 1}^{m} (1-q^i)}$

$\quad \quad \displaystyle = \displaystyle \frac{(1-q^m)\displaystyle \prod_{i = n-m+1}^{n-1} (1-q^i) + q^m(1-q^{n-m}) \displaystyle \prod_{i = n-m+1}^{n-1}(1-q^i)}{\displaystyle \prod_{i = 1}^{m} (1-q^i)}$

整理得到，$\displaystyle \frac{\displaystyle \prod_{i = n-m+1}^{n} (1-q^i)}{\displaystyle \prod_{i = 1}^{m} (1-q^i)} = {n \brack m}_q$

于此同时，令 $m = n-m$ 还可以得到

$\displaystyle {n \brack m}_q = q^{n-m} {n-1 \brack {m-1}}_q + {n-1 \brack{m}}_q$

这个式子还有一个组合意义，建立一个纵向 $[0, n]$，横向 $[0, m]$ 的 $n \times m$ 的网格
从 $(0, 0)$ 开始，每一次往上或者往右走一步，最后到达 $(n-m, m)$
在所有可能经过的路径中，路径右下方网格数为 $\text{cnt}$，那么 $\displaystyle {n \brack m}_q$ 就表示 $\displaystyle \sum {q^{\text{cnt}}}$

证明用递推，从 $(0, 0) \to (n-m, m)$ 的路径中，到达 $(n-m, m)$ 的上一步，它的位置要么是 $\displaystyle {n-1 \brack m}_q$
要么在 $\displaystyle {n-1 \brack {m-1}}_q$ 处
如果从 $(n-m-1, m) \to (n-m, m)$ 右下方是没有格子的，直接把方案数 $\displaystyle {n-1 \brack {m}}_q$ 加到答案中
如果在 $\displaystyle (n-m-1, m-1) \to (n-m, m)$，这个时候我们整体向右平移
即将此时格子的起点向右平移一个单位，那么恰好是从横轴 $1$ 这个位置出发，对应的方案数是 $\displaystyle {n-1 \brack {m-1}}_q$
因为平移的缘故，此时 $\displaystyle {n-1 \brack {m-1}}_q$ 恰好和最右边重合，右下方也是没有网格的
只不过平移了 $1$ 个单位，原先的 $\text{cnt} += n-m$，对应到表达式中，表示成 $\displaystyle q^{n-m} {n-1 \brack {m-1}}_q$

性质3

$\displaystyle \prod_{i = 0}^{n-1} (1 + q^i y) = \displaystyle \sum_{i = 0}^{n} q^{\displaystyle \binom{i}{2}} {n \brack i}_q y^i$

证明的过程用数学归纳法
$n = 1$，显然成立
$n > 1$ 对 $i$ 归纳，$\displaystyle (1+q^{n-1} y) \prod_{i = 0}^{n-2}(1+q^i y) = (1+q^{n-1}y) \sum_{i = 0}^{n-1} q^{\displaystyle \binom{i}{2}} {n-1 \brack i}_q y^i$

$\quad \quad = \displaystyle \sum_{i = 0}^{n-1} q^{\displaystyle \binom{i}{2}} {n-1 \brack i}_q y^i + \sum_{i=1}^{n} q^{n-1} q^{\displaystyle \binom{i-1}{2}} {n-1 \brack i-1}_q y^i$

注意到 $\displaystyle q^{n-1} = q^{n-i} \cdot q^{i-1}$，$\quad q^{\displaystyle \binom{i-1}{2}} \cdot q^{i-1} = q^{\displaystyle \binom{i}{2}}$

$\quad \quad = \displaystyle \sum_{i = 0}^{n} q^{\displaystyle \binom{i}{2}} \left({n-1 \brack i}_q + q^{n-i} {n-1 \brack {i-1}}_q \right) y^i = \sum_{i = 0}^{n} q^{\displaystyle \binom{i}{2}} {n \brack i}_q y^i$

下面来研究其组合意义
注意到展开形式形如 $\displaystyle \sum \displaystyle \binom{n}{i} \left(q^i \right)^i y^i$
其组合意义是，从 $n$ 个元素中选出 $i$ 个元素构成集合 $S$，$|S| = i$

那么选 $i$ 个元素，该怎么选呢？注意到，编号为 $i$ 之前的元素，即 $[0\cdots i-1]$，只有两种可能，选 $\textbf{or}$ 不选
注意到 $\displaystyle \binom{i}{2} = 0 + 1 + \cdots i-1$

由此，可以变形为 $\displaystyle (q^0 \cdot q^{i}) \cdot (q^1 \cdot q^{i-1}) \cdots (q^{i-1} \cdot q^1) \cdot \displaystyle \binom{n}{i}$
假设在 $[0 \cdots i-1]$ 中选了 $j$ 个元素，那么因为 $\displaystyle \prod_{i = 0}^{n-1} (1 + q^i y)$ 中有因子 $q$
所以对答案有 $q^j$ 的贡献

$\displaystyle \left(q^0 q^1 \cdots q^{i-1} \right) \cdot \left(\prod_{j = 1}^{i} q^j \right) \cdot \binom{n}{i}$
其中 $\displaystyle \left(q^0 q^1 \cdots q^{i-1} \right)$ 可以看作编号 $[0, i-1]$ 个元素中选择了 $(0, 1, \cdots, i-1)$ 个

$\displaystyle \left(\prod_{j = 1}^{i} q^j \right) \cdot \binom{n}{i}$ 表示编号 $[0, i-1]$ 这些元素没有被选择的个数

$\displaystyle {n \brack i}_q$ 组合意义就可以表示，在一个长度为 $S$ 的序列中选 $i$ 个元素
编号在 $[0, i-1]$ 的元素没有被选的个数为 $j$，$j \in [1, i]$，记 $\displaystyle \prod_{j = 1}^i q^j$

$\displaystyle {n \brack i}_q = \binom{n}{i} \displaystyle \left(\displaystyle \prod_{j = 1}^i q^j \right)$

性质4

$\displaystyle {n+m \brack k}_q = \sum_{i = 0}^{k} q^{(n-i)(k-i)} {n \brack i}_q {m \brack k-i}_q$

证明可以根据组合意义
在长度为 $n+m$ 的序列中，取集合 $S$，$|S| = k$，不妨将其分为 $2$ 部分，左边有 $n$ 个元素，右边有 $m$ 个元素
记左边编号 $[0, i-1]$ 没有被选择的元素个数为 $lj$，右边 $[0,i-1]$ 没有被选择的部分为 $rj$
记左边集合为 $|S_l|$，右边集合为 $|S_r|$

可以枚举 $|S_l|$，那么对于特定的 $|S_l|$
左边的贡献为 $\displaystyle \prod_{|S_l|} {q^{lj}}$，注意还有 $n - |S_l|$ 个残留元素未被选择

于是右边的贡献为 $\displaystyle \prod_{|S_r|} q^{rj + n - |S_l|} = \displaystyle q^{|S_r|(n - |S_l|)} \left(\prod_{|S_r|} q^{rj} \right)$
这样对于特定的 $|S_l|$，其贡献是

$\displaystyle q^{|S_r|(n - |S_l|)} \displaystyle \prod_{|S_l|} q^{lj} \cdot \displaystyle \prod_{|S_r|} q^{rj}$

其中 $\displaystyle \prod_{|S_l|} q^{lj}$ 就是 $\displaystyle {n \brack i}_q$，$\displaystyle \prod_{|S_r|} q^{rj}$ 就是 $\displaystyle {m \brack k - i}_q$
而 $|S_l| = i, \quad |S_r| = k - i$，代入即可

性质5

$\displaystyle {n+m+1 \brack n+1}_q = {n+m+1 \brack m}_q = \sum_{i = 0}^{m} q^i {n+i \brack n}_q$

证明，不断展开性质 2 的递推

$\displaystyle {n \brack m}_q = {n-1 \brack m-1}_q + q^m \cdot {n-1 \brack m}_q$

$\quad \quad = \displaystyle q^m {n-1 \brack m}_q + q^{m-1} \cdot {n-2 \brack m-1}_q + \cdots = \sum_{i = 0}^{m} q^i {n-(m-i+1) \brack i}_q$

性质6

$\displaystyle \frac{1}{\displaystyle \prod_{i = 0}^{n} \left(1- q^i x \right)} = \sum_{i \geqslant 0} x^i {n+i \brack n}_q$

证明用数学归纳法，对 $n$ 归纳，$n = 0$ 时候显然成立，记原式为 $F$

根据性质 2，可以有 $\displaystyle {i+n \brack n}_q = {i+n-1 \brack n-1}_q + q^n {i+n-1 \brack n}_q$，从而

$\displaystyle F = \sum_{i \geqslant 0} x^i {i+n-1 \brack n-1}_q + q^n \sum_{i \geqslant 0} x^i {i+n-1 \brack n}_q$，令 $i \leftarrow i-1$

$\displaystyle \quad \quad = \sum_{i \geqslant 0} x^i {i+n-1 \brack n-1}_q + q^n\cdot x \sum_{i \geqslant 0} x^i {i+n \brack n}_q$
根据归纳假设，可以有

$\displaystyle \frac{1}{\displaystyle \prod_{i = 0}^{n-1} \left(1-q^i x\right) } + q^n F = F$，证毕

性质6非常重要，因为可以转化成为生成函数问题

实际上，$\displaystyle [x^i] \frac{1}{\displaystyle \prod_{i = 0}^{n} \left(1- q^i x \right)} = {n+i \brack n}_q$

q-binomial 实践

Codeforces Round #752 (Div. 1)
F. October 18, 2017

先来看一个经典问题，从 $n \times m$ 的矩阵中选择一组 $n$ 个线性无关的向量的方案数（$0-1$ 向量）
这个方案数为 $\displaystyle \prod_{i = 1}^{n} (2^m - 2^{i-1})$

首先来看对于 $k$ 列的子空间，选择非 $0$ 向量的方案数为 $2^k - 1$ 种，记为 $\bm{P}(k) = 2^k - 1$
证明很简单，$k$ 列子空间每一列都可以放 $0$ 或者是 $1$，这样有 $(2^k - 1)$ 种不同的非零向量
这些非零向量一定是线性无关的

下面考虑构造向量 $a_i$，假设 $\left<a_1, a_2, \cdots, a_{i-1} \right>$ 已经构造好了
$a_i$ 要和它们都线性无关，$i = 4$ 时如下所示

$$\left( \begin{array}{c|c} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ & \cdots & \\ 1 & 1 & 1 \end{pmatrix} & \text{\Large 0} \\ \hline \begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ & \cdots & \\ 1 & 1 & 1 \end{matrix} & \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ & \cdots & \\ 1 & 1 & 1 \end{matrix} \end{array} \right)$$

因为 $\left<a_1, a_2, \cdots, a_{i-1} \right>$ 已经构造出来了，它们线性无关
化为行阶梯形矩阵，这些矩阵张成的空间 $\text{span}(i-1)$ 秩为 $i-1$，换句话说
行阶梯形矩阵最高为 $1$ 的位，恰好在列 $[0, 1, \cdots, i-1]$ 上

于是考虑 $\left<a_1, a_2, \cdots, a_{i-1} \right>$ 张成的 $i-1$ 列子空间中，有多少个线性无关向量
答案很显然是 $\bm{P}(i-1) = 2^{i-1} - 1$

那么加入向量 $a_i$，有几种选择方法呢？它肯定不能取 $\displaystyle \binom{\bm{P}(i-1)}{1}$ 中任意一种
否则就和 $\left<a_1, a_2, \cdots, a_{i-1} \right>$ 相关了，而总的选择数为 $2^{m} - 1$

所以构造 $a_i$ 能选择的方案数为 $\displaystyle (2^m - 1) - (2^{i-1} - 1) = (2^m - 2^{i-1})$

根据乘法原理，最后的答案是 $\displaystyle \prod_{i = 1}^{n} \left(2^m - 2^{i-1} \right)$

October 18, 2017

题目大意，给出 $n, k, x$，选一个 $n$ 元组，使得所有数都 $< 2^k$，并且满足任意一个子集的异或和不等于 $x$

算法分析，该问题等价于，将每个数写成二进制形式，$n \times k$ 的 $01$ 矩阵中
有多少个秩为 $k$ 的子矩阵，使得这些矩阵张成的向量空间中不包括 $x$

直观点说，秩为 $k$ 就是化为行阶梯形之后，最高为 $1$ 的位分别在第 $[1, 2, \cdots, k]$ 位上
注意这里需要特别考虑包不包括 $\bm{0}$ 向量，一般来说，不包括 $\bm{0}$ 向量的话
秩为 $k$ 的线性空间中，可以放 $2^{k} - 1$ 个线性无关向量

算法设计

$\textbf{(1)}$
首先，如果 $x = 0$ 时等价于秩序为 $k$ 的（即最高的 $1$ 在第 $k$ 位） $n$ 元组线性无关

此时答案就是 $\displaystyle \prod_{i = 1}^{n} \left(2^{k} - 2^{i-1} \right)$

具体的分析见上面
简单来说，第 $i-1$ 个向量可以选择的范围是 $\displaystyle (\underbrace{00\cdots 0}_{i-1 \text{位}} \longrightarrow \underbrace{ 11\cdots 1 }_{i-1 \text{位}})$

用递推的思想，在 $i-1$ 个向量的基础上构造出第 $i$ 个向量，这 $\left(2^{i-1} - 1 \right)$ 个都不能选
否则就线性相关了，所以第 $i$ 个向量方案数为 $\displaystyle (2^{k} - 1) - (2^{i-1} - 1) = 2^{k} - 2^{i-1}$

$\textbf{(2)}$
假设 $x \neq 0$，那么此时总的方案数依然是 $tot = \displaystyle \prod_{i = 1}^{n} \left(2^{k} - 2^{i-1} \right)$
只不过需要减掉不符合条件的，也就是说，要减去一个方案数 $P$
$P$ 由 $2$ 部分构成，第一部分是在 $tot$ 中选出非 $0$ 向量 $x$，然后考虑将剩下的非线性相关向量构造成基

(2.1)
假设线性空间的维度是 $r$，考虑 $r \times k$ 的线性空间，所有线性无关的方案为 $\displaystyle \prod_{i = 1}^{r} \left(2^{k} - 2^{i-1} \right)$

那么对于 $r \times k$ 的线性空间，有 $r$ 个基，如果 $x$ 可以由这些基的一个或者多个线性表出的话，那么肯定不符合条件
$r$ 个基，每个基都可以选或者不选，不能一个也不选，所以构造 $x$ 的方案数为 $\displaystyle (2^r - 1)$

那么此时我们得到 $\left<x, a_2, a_3, \cdots, a_r \right>$
构造 $\left<a_2, a_3, \cdots, a_r \right>$ 的方案数是 $\displaystyle \prod_{i = 2}^{r} \left(2^k - 2^{i-1} \right)$

所以对于 $r \times k$ 的线性空间，方案数为

$\displaystyle \prod_{i = 1}^{r} (2^{k} - 2^{i - 1})- \displaystyle (2^r - 1) \prod_{i = 2}^{r} (2^k - 2^{i-1}) = \displaystyle \prod_{i = 1}^{r} (2^k - 2^{i-1}) (2^k - 2^r)$

$\displaystyle \quad \quad = \prod_{i = 1}^{r} \left(2^k - 2^i \right)$

(2.2)
最后，考虑剩下的 $n-r$ 个向量如何构造？
实际上，经过上面的构造，对于 $r \times k$ 的线性空间是满足条件的，接着剩下的 $n-r$ 个向量
考虑由 $r \times k$ 的线性空间的基线性表出即可

对于 $(n-r)$ 个向量，考虑将其由前 $i$ 个基表示其中一部分，前 $i+1$ 个基再表示一部分，以此类推
对于前 $i$ 个基，一共可以取 $2^i$ 个不同的线性基，（包括 $\bm{0}$ 向量）
所以可以表示 $(n-r)$ 个向量其中的任意 $0, 1, 2, \cdots, n-r$ 个

也就是说，对于前 $i$ 个基，能构造出来的方案数为
$\displaystyle (1 + 2^i + \left(2^i \right)^2 + \left(2^i \right)^3 + \cdots)$

所以用前 $r$ 个线性基构造剩下的 $n-r$ 个向量的方案为

$\displaystyle \prod_{i = 0}^{r} \left(1 + 2^i + (2^i)^2 + \cdots \right)$

这里很自然地想到用生成函数，构造 $n-r$ 个向量方案数实际上就是

$\displaystyle [x^{n-r}]\prod_{i = 0}^r \left(1 + 2^i x + \left(2^i x \right)^2 + \left(2^i x \right)^3 + \cdots \right) = [x^{n-r}] \displaystyle \prod_{i = 0}^{r} \displaystyle \frac{1}{1- 2^i x}$

这个实际上就是 q-binomial 的生成函数

$\displaystyle [x^{n-r}] \prod_{i = 0}^{r} \displaystyle \frac{1}{1- 2^i x} = {r + n - r \brack r}_2 = {n \brack r}_2$

(2.3)

那么这部分答案就出来了

$\displaystyle \sum_{r = 0}^{n} \displaystyle \prod_{i = 1}^{r} \left(2^k - 2^i \right) {n \brack r}_2$

q-binomial 按定义展开即可

$\displaystyle {n \brack r}_2 = \displaystyle \frac{[n]!_2}{[r]!_2 \cdot [n-r]!_2}$

其中 $[n]!_2 = [1]!_2 \cdot [2]!_2 \cdot [3]!_2 \cdots [n]!_2 = \displaystyle \prod_{i = 1}^{n} \frac{1-2^i}{1-2} = \prod_{i = 1}^{n} (2^i - 1)$

这些东西全部可以在 $O(n)$ 时间复杂度内预处理完成

实现过程中的细节

首先可以预处理q-binomial的相关项

$\displaystyle f(p) = \prod_{j = 1}^{p} (2^p - 1)$ 很容易在 $O(n)$ 时间复杂度内预处理出来

记 $\displaystyle \text{inv}(p) = \frac{1}{2^p - 1} = \frac{1}{f(p)} \cdot f(p-1)$

于是考虑从 $p \in (n \to 1)$ 递推，更新 $\displaystyle \frac{1}{f(p)} \leftarrow \frac{1}{f(p-1)}$

只要令 $\displaystyle x \leftarrow \frac{1}{f(p)}$，然后不断令 $x \leftarrow x \cdot (2^p - 1)$ 即可

考虑如何计算 $\displaystyle \frac{\displaystyle \prod_{j = 1}^{n} (2^j - 1)}{\displaystyle \prod_{j = 1}^{r} (2^j - 1) \cdot \displaystyle \prod_{j = 1}^{n-r} (2^j - 1)}$

可以令 $Q(r) = \displaystyle \frac{\displaystyle \prod_{j = 1}^{n} (2^j - 1)}{\displaystyle \prod_{j = 1}^{n-r} (2^j - 1)}$

这样 $r \in (1 \to n)$ 遍历的时候，$Q(r)$ 一开始只有 $\displaystyle (2^n - 1)$ 这一项
由于 $n$ 比较大，此时令 $2^n = pn$，用乘法逆元进行计算

递推的时候，一开始令 $Q(r) = \displaystyle (pn - 1)$，然后 $Q(r)$ 每一次要除掉一个 $\displaystyle \frac{1}{2^{r} - 1}$

这一项已经预处理出来了，就是 $Q(r) \leftarrow Q(r) \cdot \text{inv}(r)$，更新 $Q(r) \leftarrow Q(r) \cdot (2^k - 2^r)$

此时 $r$ 这一项对应的值已经求完了，将 $ans += Q(r)$

接着更新 $pn = pn / 2$ （用 $2$ 的逆元计算），然后令 $Q(r) \leftarrow Q(r) \cdot (pn - 1)$
就可以递推到 $r \leftarrow r + 1$ 的情况进行计算了

最后注意，$r = 0$ 的情况还没有统计，实际上 $r = 0$ 时方案数就是 $1$
$ans += 1$ 即可

const int maxn = 1e7 + 10;
const int N = 1e7;

mint inv[maxn], fac[maxn], infac[maxn];
mint pw[maxn], f[maxn];

void get_pw2() {
    pw[0] = 1;
    for (int i = 1; i <= N; i++) pw[i] = pw[i-1] * mint(2);
}

void pre() {
    fac[0] = mint(1);
    for (int i = 1; i <= N; i++) fac[i] = fac[i-1] * mint(pw[i].x - 1);

    mint Q = fac[N].inv();
    for (int i = N; i >= 1; i--) {
        inv[i] = Q * fac[i-1];
        Q *= (pw[i] - 1);
    }
}

int solve1(int n, int k) {
    if (k == 0 or n > k) return 0;
    mint ans = mint(1);
    for (int i = 0; i < n; i++) ans = ans * (pw[k] - pw[i]);
    return ans.x;
}

void solve2(int n, int k) {
    mint inv2 = mint(2).inv();

    mint ans = 0;
    mint Q = mint(1);

    mint pn = power(mint(2), n);
    for (int r = 0; r < k; r++) {
        ans += Q;

        Q *= inv[r+1] * (pn - 1);
        Q *= (pw[k] - pw[r+1]);
        pn *= inv2;
    }

    printf("%d\n", ans.x);
}

int main() {
    freopen("input.txt", "r", stdin);
    get_pw2();
    pre();

    int cas;
    cin >> cas;
    while (cas--) {
        int n, k, x;
        scanf("%d%d%d", &n, &k, &x);

        if (x == 0) {
            int ans = solve1(n, k);
            printf("%d\n", ans);
        }
        else {
            solve2(n, k);
        }
    }
}