高斯二项式系数是二项式系数的 “q-analog” ，对于处理求所有排列逆序数指数和的问题往往可以产生“降维打击”的效果。
前言
在牛客多校训练赛 9 中，我们队第一次遇到了高斯二项式系数的题目，当时并没有学过相关的理论，cyy 用一种高级的 dp 过掉了那道题。看到题解上“高斯二项式系数”这个名词之后，我们就学习了一番。之后又碰到了一道 Opencup 题，发现它正是 01 序列所有排列逆序对指数之和这一问题，于是很快在前中期秒杀了。看到题解的朴素 dp 的方法，顿时感觉这一工具的强大，这里做一总结。维基百科链接
定义与性质
定义1 定义 q number 如下：
$$
[k]q = \sum{0\leq i < k} q^i = 1+q+q^2+\ldots+q^{k-1} = \begin{cases} \frac{1-q^k}{1-q} & q \neq 1,\
k & q = 1
\end{cases}
$$
定义2 定义高斯二项式系数如下：
$$
\binom{m}{r}_q = \frac{[m]_q [m-1]_q \cdots [m-r+1]_q}{[1]_q [2]_q \cdots [r]_q} \text{ }(r \leq m)
$$
一种等价定义如下，不过好像没有什么用：
$$
{m \choose r}_q
= \begin{cases}
\frac{(1-q^m)(1-q^{m-1})\cdots(1-q^{m-r+1})} {(1-q)(1-q^2)\cdots(1-q^r)} & r \le m \
0 & r>m \end{cases}
$$
类似组合数，可以定义 q factorial 如下：
$$
[n]_q! = [1]_q [2]_q \cdots [n]_q
$$
这样，我们就有一个漂亮简洁、易于编程的类似组合数的高斯二项式系数公式了：
$$
\binom nr _q = \frac {[n]_q!}{[r]_q! [n-r]_q!}
$$
例子
$$
{0 \choose 0}_q = {1 \choose 0}_q = 1
$$
$$
{m \choose 0}_q = {m \choose m}_q =1
$$
$$
{4 \choose 2}_q = \frac{[4]_q[3]_q}{[1]_q[2]_q} = \frac{(1+q+q^2+q^3)(1+q+q^2)}{1\cdot (1+q)}=(1+q^2)(1+q+q^2)=1+q+2q^2+q^3+q^4
$$
性质1 （高斯二项式系数的组合意义）考虑 $n$ 个数组成的数列，其中有 $r$ 个 1 ，$n-r$ 个 0，那么组成的数列恰好有 $d$ 个逆序对数的方案数就是关于 $q$ 的多项式 $\displaystyle \binom nr _q = \frac {[n]_q!}{[r]_q! [n-r]_q!}$ 的 $q^d$ 项系数。
例如：$m=4,r=2$ 时，$\displaystyle \binom 42_q = 1+q+2q^2+q^3+q^4$ ，而 0011 的 6 种排列恰好有 1,1,2,1,1 种方式逆序数分别为 0,1,2,3,4。
性质 1 就是解决很多题目的利器。最典型的题目就是下面的了：给定长度为 $n$ 的 01 序列 $a$ ，记序列 $a$ 的所有排列的集合为 $F(a)$，序列 $b$ 的逆序对数为 $r(b)$ ，求 $\displaystyle \sum_{b \in F(a)} q^{r(b)}$ ，答案直接就是高斯二项式系数。
可是如果序列 $a$ 不止有 01 这两种元素，怎么办呢？我们有下面的推广：
性质1‘ （多重高斯二项式系数）设 $a$ 是由 $n$ 个数组成的数列，假设 $a$ 中有 $m$ 种元素，其中元素 $x_i$ 有 $c_i$ 个 $(1\leq i \leq m)$。类比组合数与多重组合数的关系，答案就是下面的“多重”高斯二项式系数：
$$
\binom{n}{c_1,c_2,\cdots,c_m} = \frac{[n]_q!}{[c_1]_q! [c_2]_q! \cdots [c_m]_q!}
$$
值得一提的是，在这个公式里，我们只关心 $c_i$ 的大小，而不关心 $x_i$ 的取值、大小关系等等。
例题
Inversions of all permutations
题意
给定任意可重序列 $a$ ，记序列 $a$ 的所有排列的集合为 $F(a)$，序列 $b$ 的逆序对数为 $r(b)$ ，求 $\displaystyle \sum_{b \in F(a)} q^{r(b)}$ 。
题目来源：2019牛客暑期多校训练营（第九场）
题解
直接使用性质 1b 即可，复杂度 $O(n\log n)$。
性质1b （多重高斯二项式系数）设 $a$ 是由 $n$ 个数组成的数列，假设 $a$ 中有 $m$ 种元素，其中元素 $x_i$ 有 $c_i$ 个 $(1\leq i \leq m)$。类比组合数与多重组合数的关系，答案就是下面的“多重”高斯二项式系数：
$$
\binom{n}{c_1,c_2,\cdots,c_m} = \frac{[n]_q!}{[c_1]_q! [c_2]_q! \cdots [c_m]_q!}
$$
Do I Wanna Know
题意
有 $n$ 只编号分别为 $1,2,\ldots,n$ 的猴子两两打架，任意编号小的猴子打赢编号大的猴子的概率均为 $p$ ，输掉概率均为 $q=1-p$ 。问对于所有 $k=1,2,\ldots,n-1$ ，下面的局面出现的概率是多少：存在方案可以将猴子分为包含 $k$ 只猴子的强者组和包含 $n-k$ 只的弱者组，使得强者组的每只猴子都打赢了弱者组的每只猴子。
题解
显然如果存在，那么强者组的选取是唯一的。将强猴子记为1，弱猴子记为 0 ，对每个 k 相当于求 k 个 1 与 $n-k$ 个 0 的所有排列出现概率之和。考虑如果给定一种排列 $P$，记其逆序数为 $c$ ，那么它出现的概率就是 $p^c q^{k(n-k) - c}$ 。将这个式子求和，整理得到：
$$
q^{k(n-k)}\sum_{b \in F(a)} (\frac pq )^{r(b)} = q^{k(n-k)} \binom{n}{k}_\frac pq
$$
1 | /* |