q-analog 初探

· · 个人记录

每次都因为睡觉搁置了写笔记的安排，这次一定不能咕。

好吧就是抄了一遍 PPT，q-Lucas 的证明之后抄飘飘的。

q-analog（即 q-模拟），是对于一个对象 u 构造一个关于 q 的表达式 f(q)，使得：

\lim_{q \to 1} f(q) = u

这是一个比较 general 的定义。这里 q 可以是一个形式幂级数，也可以是一个比较具体的值，可以具体问题具体分析带入合适的 q。实际上 q 的意义就是对同一个对象附上不同的组合意义，得到一个生成函数或者是一个具体对象；而 q=1 的时候这个具体的对象刚好就是 u。

好吧，比较抽象。我们先举出几个比较简单的对象的 q-analog。

验证容易发现，在 q 趋近于 1 的时候，[n]_q = n（可以直接洛）。

这个展开的形式也比较简便，就不费这点心思写公式了。

不知道有没有什么广义二项式系数的 q-模拟，既然是初探那就暂时不管吧！

可以对照组合数理解。容易发现 q=1 的时候就是组合数，现在能否理解 q-模拟 想做的事情了？

如果看到下面没有 q 的下标自动补上就好了 ×

接下来研究一些定理。主要研究二项式系数。

定理 1：记 S_n 为所有 n 阶排列构成的集合，\tau(p) 为排列 p 的逆序对数，有：

\sum_{p \in S_n} q^{\tau(p)} = [n]_q !

证明：

有一个结论是，记 c_i 为排列中以 i 为第二个元素的逆序对个数（就是逆序对 (x,i),x<i 的个数），那么一个序列 c 和一个排列唯一对应，反之亦然（可以看这个题）。

继续分析 [n]_q ! 本身。容易发现 [i]_q 的生成函数相当于在枚举 c_i，对应每一个排列，定理得证。

可以写出一个代数证明，但是我懒了。

定理 1.5：记 S_n 为 a_1 个 1，a_2 个 2，……，a_k 个 k 构成的排列集合，\tau(p) 为序列 p 的逆序对数，有：

\sum_{p \in S_n} q^{\tau(p)} = \begin{bmatrix} n \\ a_1,a_2,\cdots ,a_k \end{bmatrix}_q

此定理 k=2 的特殊情况将在之后证明，k>2 的情况可以推广而来不再证明。

定理 2：（排列从 1 开始编号）记 \displaystyle \tau(p) = \sum_{i\in S_p} i ，其中 S_p = \{i \mid p_i>p_{i+1}\}。记 S_n 为 a_1 个 1，a_2 个 2，……，a_k 个 k 构成的排列集合，有：

\sum_{p \in S_n} q^{\tau(p)} = \begin{bmatrix} n \\ a_1,a_2,\cdots ,a_k \end{bmatrix}_q

容易发现形式和定理 1.5 的形式一模一样。这说明了降位和和逆序对的分布是相同的。这个给出一个合理的组合意义解释非常困难，可以看论文。

定理 3：若 n \geq 1，则有 \begin{bmatrix} n \\ m \end{bmatrix}_q = \begin{bmatrix} n-1 \\ m-1 \end{bmatrix}_q + q^m\begin{bmatrix} n-1 \\ m \end{bmatrix}_q。

有简单的代数证明，但是代数推导天地灭，这不优秀啊！

我们先假定这个是对的，带入 n = n+m，可以得到：

这个式子显然跟我们的定理等价。记网格图上从 $(0,0)$ 只向上或向右到 $(n,m)$ 的路径的集合为 $S$，路径 $p$ 右下角（或左上角）的格子个数为 $\tau(p)$，容易发现 $\displaystyle \begin{bmatrix} n+m \\ n \end{bmatrix}_q = \sum_{p \in S} q^{\tau(p)}$。这给出了一个递推式的形式，容易发现初值对应，定理得证。 然后是 $\operatorname{q-Catalan}$。有 $\operatorname{Cat}(n)_q = \dfrac{\begin{bmatrix} 2n \\ n \end{bmatrix}_q}{[n+1]_q} = \begin{bmatrix} 2n \\ n \end{bmatrix}_q - \begin{bmatrix} 2n \\ n+1 \end{bmatrix}_q$。 给它一个组合意义：记所有长度为 $2n$ 的合法出入栈序列集合为 $S$，$\tau(p)$ 为序列 $p$ 的降位和，则 $\operatorname{Cat}(n)_q = \sum_{p \in S} q^{\tau(p)}$。 定理 4（$q$-二项式定理）： $$ \prod_{i=0}^{n-1} (1+q^iy) = \sum_{i=0}^n q^{\frac{i(i-1)}{2}} \begin{bmatrix} n \\ i \end{bmatrix}_q y^i $$ 我们继续考虑一个组合意义。$[y^c]\prod_{i=0}^{n-1} (1+q^iy)$ 相当于一个 $n$ 列的直方图，第 $i$ 列共有 $i-1$ 个格子，选 $c$ 列出来。对于选出来的 $c$ 列，先把选出来的第 $i$ 列上面 $i-1$ 个格子削掉（共有 $\dfrac{i(i-1)}{2}$ 个格子，容易发现不存在没有东西削的情况），然后剩下的所有列，上一列一定不比当前列高。这样的话就是算从 $(0,0)$ 走到 $(c,n-c)$ 所有路径的权值，一条路径的权值定义为，设其右下角的格子个数为 $c$，$q^c$（总之就是直接沿用二项式系数的定义），那么显然就是 $\begin{bmatrix} n \\ i \end{bmatrix}_c$。 定理 5： $$ \begin{bmatrix} n+m \\ k \end{bmatrix}_q = \sum_{i=0}^k q^{(n-i)(k-i)} \begin{bmatrix} n \\ i \end{bmatrix}_q \begin{bmatrix} m \\ k-i \end{bmatrix}_q $$ 类似于范德蒙德卷积。 再给一个组合意义证明。$\begin{bmatrix} n+m \\ k \end{bmatrix}_q$ 可以用 $n+m$ 个数里有 $k$ 个 $1$，然后用逆序对（实际上在这里取用的是顺序对）那套意义去理解。和式里面就是枚举前 $n$ 个里面有 $i$ 个 $1$，算左右两边的逆序对，然后补上两块之间的逆序对。 定理 6： $$ \begin{bmatrix} n+m+1 \\ n+1 \end{bmatrix}_q = \sum_{i=0}^m q^i\begin{bmatrix} n+i \\ n \end{bmatrix}_q $$ 使用定理 3，重复展开即可证明。组合意义也是考虑走网格图，比较通用的证明方法。 定理 7（$q$-二项式定理-负指数形式）： $$ \prod_{i=0}^{n-1} \dfrac{1}{1-q^ix} = \sum_{i=0}^{+∞} \begin{bmatrix} n+i-1 \\ i \end{bmatrix}_q x^i $$ 还是考虑 $[x^c]\prod_{i=0}^{n-1} \dfrac{1}{1-q^ix}$。相当于 $c$ 列，每列都不大于 $n$ 的直方图，以格子大小为指数，也即从 $(0,0) \to (i,n-1)$ 所有路径的权值，一条路径的权值定义为，设其右下角的格子个数为 $c$，$q^c$（总之就是直接沿用二项式系数的定义）。想必不用我多说了吧。 定理 8（$\operatorname{q-Lucas}$）：有一个模分圆多项式的基本形式，CRT 之后可以得到新形式（其中 $n/d$ 为 $n$ 除以 $d$ 向下取整的值）： $$ \begin{bmatrix} n \\ m \end{bmatrix}_q = \dbinom{n \bmod d}{m \bmod d} \begin{bmatrix} n / d \\ m / d \end{bmatrix}_q $$ 其中 $q=e^{2ci\pi/d}$，且 $\gcd(c,d)=1$。 证明不会。 要对于一个具体的 $q$ 算 q-二项式系数的值的话，令 $d = \operatorname{ord}(q)$，有： $$ \begin{bmatrix} n \\ m \end{bmatrix}_q = \begin{bmatrix} n/d \\ m/d \end{bmatrix}_q \dbinom{n \bmod d}{m \bmod d} $$ 接下来研究 q-analog 的应用。首先要知道这些东西怎么算。 比如研究 $[n]_q !$ 的前 $k$ 项，先展开：$[n]_q ! = \dfrac{(1-q)(1-q^2)\cdots (1-q^n)}{(1-q)^n}$。 法一：这个东西，显然可以使用多项式 $\exp$ 算，求导再求积（付公主的背包），时间复杂度 $O(n \log n)$，延展性并不强。 法二：背包，显然最多只能选 $O(\sqrt k)$ 个数，最后再做个多项式卷积，时间复杂度 $O(n \sqrt n)$，复杂度取决于分母的计算复杂度。 法三：五边形数，显然这里有值的位置比较稀疏，仍然是多项式卷积，时间复杂度 $O(n \sqrt n)$。 法四：杨表。不是很会这个东西。 法五：采用 q-二项式定理对分子变形： $$ [n]_q ! = \dfrac{(1-q)(1-q^2)\cdots (1-q^n)}{(1-q)^n} = \prod_{i=0}^{n-1}(1-q \cdot q^i) = \sum_{i=0}^n (-1)^i q^{\frac{(i+1)i}{2}} \begin{bmatrix} n \\ i \end{bmatrix}_q $$ 变形之后，如果算前 $k$ 项，那么 $\sum$ 的上指标就会缩减到 $O(\sqrt k)$ 级别。 然后考虑每一项的生成函数。注意到 $\begin{bmatrix} n \\ m+1 \end{bmatrix}_q = \begin{bmatrix} n \\ m \end{bmatrix}_q \dfrac{1-q^{n-m}}{1-q^{m+1}}$（考虑 q-二项式系数 的定义）。这样的话就可以 $O(k)$ 递推，总时间复杂度 $O(k \sqrt k)$。 这样算 $[n]_q!f(q)$ 也能 $O(k \sqrt k)$ 算了，延展性比较高。 通过分拆数这个工具引出 $\begin{bmatrix} n \\ m \end{bmatrix}_q$ 的另一个组合意义： $$ \begin{bmatrix} n \\ m \end{bmatrix}_q = [t^n] \dfrac{1}{1-t} \prod_{i=1}^m \dfrac{1}{1-q^it} $$ 仍然考虑网格图，走出来的路径其实也就是一个 Ferrers 图像。上面的很多东西也可以这么解释。有个不用 q-analog，但是用到了 Ferrers 图像相关性质的题，可以看[山河重整 - Sol](https://www.luogu.com.cn/blog/blog10086001/solution-p8340)。 对于 $q$ 有具体取值的也可以做，具体考虑快速阶乘（复杂度 $O(\sqrt n\log n)$）的做法。 考虑一些有限域下的矩阵计数。有两个简单的小 intro： 求 $\mathbb{F}_q^n$（意思是 $n$ 维的模 $q$ 意义下的空间）的向量个数：显然是 $q^n$。 求 $\mathbb{F}_q^n$ 上的 $n \times n$ 的矩阵个数：显然是 $q^{n^2}$。 然后再考虑一些比较难的问题。 求 $\mathbb{F}_q^n$ 中大小为 $k$ 的线性无关向量组个数（顺序不同也认为不同）： 第一个向量不能选零向量，方案数 $q^n-1$；第二个向量有两个不能选，方案数 $q^n-q$；第三个有四个不能选，方案数 $q^n-q^2$，以此类推。 记这个问题的答案为 $((n)_k)_q$。显然有： $$ ((n)_k)_q = \prod_{i=0}^{k-1} (q^n - q^{i}) = q^{\frac{k(k-1)}{2}} \prod_{i=n-k+1}^n(q^i-1) = \dfrac{(q-1)^k q^{\frac{k(k-1)}{2}} [n]_q!}{[n-k]_q!} $$ 求 $\mathbb{F}_q^n$ 中的 $k$ 维子空间的个数（如果选出的向量张成出同一个子空间算一样的）： 先钦定一组大小为 $k$ 的线性无关向量组当成这 $k$ 维子空间的基，方案数 $((n)_k)_q$；注意到这时每个子空间会被算 $((k)_k)_q$ 次，答案就是 $\dfrac{((n)_k)_q}{((k)_k)_q}$。 恰巧有一个结论是： $$ \begin{bmatrix} n \\ k \end{bmatrix}_q = \dfrac{((n)_k)_q}{((k)_k)_q} $$ 结论容易验证，考虑组合解释： $\begin{bmatrix} n \\ k \end{bmatrix}_q$ 描述了 $n$ 个盒子放 $m$ 个球，方案数关于是否有球生成一个 01 序列逆序对的生成函数。 $\dfrac{((n)_k)_q}{((k)_k)_q}$ 描述的是 $k$ 个行基向量消元后得到的 $k \times n$ 的上三角矩阵 $F$，算不同的消元后的矩阵（对应不同的空间）。考虑每一列，如果这一列上出现了一个新的向量，那么方案数为 $1$（消元过程已确定），否则方案数为已有向量的张成空间里任选一个的方案数，记前面有的 $1$ 的个数为 $p$，方案数就是 $q^p$。 算了，能数的东西很多（比如可对角化矩阵计数之类的……），基本上都是一样的，用两个例题结束吧。 ### CF1603F October 18, 2017 问题等价于，给定 $\mathbb{F}_2^k$ 上一个向量 $v$，有多少个 $\mathbb{F}_2^k$ 上的大小为 $n$ 的向量组不能线性表示 $v$。$k \leq 10^7,n \leq 10^9$。 这个题用组合数学的方法好像真的只评得上 2700，不是很懂。 用 q-analog 的方法考虑。 如果 $v$ 是零向量就非常好办，答案就是 $((k)_n)_2$，这个可以 $O(k)$ 算。 如果不是，我们先枚举 $r$，然后生成所有的大小为 $r$ 的不能线性表示 $v$ 的线性无关向量组。第一个向量不能是 $v$ 或者零向量，少了两种选择，第二个向量少了四种选择，类推可知方案数为 $\dfrac{((k)_{r+1})_2}{2^k-1}$。 然后还有 $n-r$ 个向量可以随机插入，这 $n-r$ 个向量要被之前的向量线性表示，用生成函数的形式写出就是 $\displaystyle [x^{n-r}] \prod_{i=0}^r \dfrac{1}{1-2^ix}$。根据定理 7 可知这个就是 $\begin{bmatrix} n \\ r \end{bmatrix}_2$。 答案就是对所有的 $r$ 求和，都可以用 $O(k)$ 的时间算出来。 ### LOJ562 Tangjz 的背包 题意：记 $\displaystyle f(v) = [x^vy^m] \prod_{i=1}^n (1+x^iy)$，求 $\displaystyle \sum_{v=1}^p 19190506^{p-v}f(v)$，其中 $p$ 是使得 $f(p) \neq 0$ 的最大整数。多组询问，$T \leq 5\times 10^5$，$n,m \leq 10^{12}$，对 $998244353$ 取模。 令 $C=19190506$。浅推一波式子： $$ \begin{aligned} \sum_{v=1}^p C^{p-v} [x^vy^m] \prod_{i=1}^n (1+x^iy) &= C^p \sum_{v=1}^p C^{-v} [x^vy^m] \prod_{i=1}^n (1+x^iy) \\ &= C^p \sum_{v=1}^p [x^vy^m] \prod_{i=1}^n (1+(C^{-1}v)^iy) \\ &= C^p [y^m] \prod_{i=1}^n (1+B^{-1}y) \\ &= C^{p-\frac{(m+1)(m+2)}{2}} \begin{bmatrix} n \\ m \end{bmatrix}_{C^{-1}} \end{aligned} $$ 最后一步运用了定理 4。 现在问题是 $p$ 是多少了……显然 $\displaystyle p = \sum_{i=n-m+1}^n i$，问题在于怎么算 $n,m$ 很大的情况下的二项式系数，可以用 $\operatorname{q-Lucas}$ 解决。