Background
这一切都要从一场模拟赛说起...... 怨念
q-analog
定义 q-模拟 $[n]_q$ 为
$$[n]_q=1+q+q^2+\cdots+q^{n-1}=\frac{1-q^n}{1-q}$$
我们可以看到当 $q\rightarrow 1$ 时，$[n]_q=n$。
q-factorial
定义 q-阶乘 $n!_q$ 为
$$n!_q=[1]_q[2]_q\cdots[n]_q$$
我们可以看到 $q\rightarrow 1$ 时，$n!_q=n!$。
q-binomial coefficient
定义 q-二项式系数 $\displaystyle{n\choose m}_q$ 为
$${n\choose m}_q=\frac{n!_q}{m!_q(n-m)!_q}$$
实际上，我们可以将其看成关于 $q$ 的生成函数，相应的组合对象是所有整数拆分，满足不超过 $n-m$ 部分，每部分不超过 $m$，$q^i$ 刻画的是满足条件的正整数 $i$ 的拆分数。
不仅 q-二项式系数的定义与通常的二项式系数形式相近，它们也有相似的性质。
我们考虑用于研究整数拆分的 Ferrers 图，满足条件的拆分即对应的 Ferrers 图不超过 $n-m$ 行 $m$ 列的拆分，我们对这样的的 Ferrers 图进行转置，得到一个不超过 $m$ 行 $n-m$ 列的图，反过来，我们也可以将不超过 $m$ 行 $n-m$ 列的 Ferrers 图转置得到不超过 $n$ 行 $n-m$ 列的图，这告诉我们
$${n\choose m}_q={n\choose n-m}_q$$
q-二项式系数满足 q-Pascal 递推关系
$${n\choose m}_q={n-1\choose m}_q+q^{n-m}{n-1\choose m-1}_q$$
证明：分两种情况：
-
满足条件的 Ferrers 图小于 $n-m$ 行，这种情况的贡献为 $\displaystyle{n-1\choose m}_q$。
-
满足条件的 Ferrers 图恰好 $n-m$ 行，所以我们可以移除第一列，得到一个不超过 $n-m$ 行 $m-1$ 列的 Ferrers 图，故这部分贡献为 $\displaystyle q^{n-m}{n-1\choose m-1}_q$。
有了这条递推关系，我们便可通过数学归纳法证明由生成函数定义的 q-二项式系数与本节开头给出的定义是等价的了。
q-binominal theorem
q-二项式定理说的是
$$\prod_{i=1}^n(1+q^ix)=\sum_{m=1}^n q^{{m+1\choose 2}}{n\choose m}_qx^m$$
当 $q\rightarrow 1$ 时，我们得到通常的二项式定理。
证明：
左边的式子可以看成不超过 $n$ 部分，且每部分不超过 $n$ 的拆分的二元 GF，其中 $q^i$ 刻画的是满足条件的正整数 $i$ 的拆分数，而 $x$ 刻画的则是拆分的部分数。
令 $a_m(q)$ 表示恰好有 $m$ 部分的合法拆分的 GF，于是我们仅需证
$$a_m(q)=q^{{m+1\choose 2}}{n\choose m}_q$$
证明也很容易，我们考虑将恰好有 $m$ 部分的合法拆分的第一行移除前 $m$ 列，第二行移除前 $m-1$ 列，......，第 $m$ 行移除第一列，这样我们就得到了一个不超过 $m$ 部分且每部分不超过 $n-m$ 的拆分，反过来做也是一样的，所以我们可以在这两类拆分之间建立双射，而后者的 GF 恰好为 $\displaystyle{n\choose m}_q$，乘上删去的列的贡献的贡献即知证毕。
那么，如何快速处理一行的 q-二项式系数呢？（取模意义下）
我们发现 q-模拟和 q-阶乘的线性处理都是 trivial 的，而瓶颈在于在于 q-二项式系数的处理时可能会出现分母为 0（在取模意义下）的情况。
设 $\alpha$ 为最小的 $i$ 使得 $q^i\equiv 1$，那么对于任意的 $i$，都有 $q^{i}\equiv q^{i\bmod \alpha}$。
我们将 q-二项式系数写成
$${n\choose m}_q=\prod_{i=1}^m\frac{1-q^{n-m+1}}{1-q^i}$$
不难发现分子分母均出现了长度为 $\alpha$ 的循环节，将每个循环节中不为 0（取模意义下）的部分提出来单独算。
那么分子分母中剩下的部分无非是形如 $(1-q^{i\alpha})$ 的连乘积，我们将 $(1-q^{i\alpha})$ 写成
$$1-q^{i\alpha}=(1-q^{\alpha})(1+q^{\alpha}+\cdots+q^{(i-1)\alpha})$$
而注意到剩下的部分分母有 $\displaystyle\left\lfloor\frac{m}{\alpha}\right\rfloor$ 项，分子有 $\displaystyle\left\lfloor\frac{n}{\alpha}\right\rfloor-\left\lfloor\frac{n-m}{\alpha}\right\rfloor$ 项，所以要么分子比分母多一项，要么分子分母项数相同。
当分子比分母多一项的时候，有 $\displaystyle(1-q^\alpha)|{n\choose m}_q$，故 $\displaystyle {n\choose m}_q\equiv 0$；
当分子分母项数相等时 $(1-q^{i\alpha })$ 这些项相互抵消，记 $\displaystyle x=\left\lfloor\frac{n}{\alpha}\right\rfloor,y=\left\lfloor\frac{m}{\alpha}\right\rfloor$，剩下部分对 $\displaystyle {n\choose m}_q$ 的贡献即为 $\displaystyle {x\choose y}$。
