每次处理全局最小值的行和列,然后把这些行和列删掉,分别相乘。
那么,相当于处理一个 L 型,每行每列都要取到上界的方案数。令 \(c\) 和 \(d\) 分别为全局最小值的行数和列数,以及全局最小值为 \(q\)。
枚举至多有 \(x\) 行,至多有 \(y\) 列能取到最大值,即有 \(c-x\) 行和 \(d-y\) 列不能取到 \(q\)。
那么,对于 L 型上的一个点,如果在钦定为不能取到 \(q\) 的行或者列上,它的取值范围是 \([1,q-1]\);反之,范围是 \([1,q]\)。
公式:
\[\begin{aligned} &\sum _x^c \sum _y^d (-1)^{c+d-x-y} \binom c x \binom d y q^{cm+dn-cd-((c-x)m+(d-y)n-(c-x)(d-y))} (q-1)^{(c-x)m+(d-y)n-(c-x)(d-y)} \\ =&\sum _x^c \sum _y^d (-1)^{c+d-x-y} \binom c x \binom d y q^{xm+yn-xd-yc+xy} (q-1)^{cm+dn-cd+xd+yc-xm-yn-xy} \\ =&(q-1)^{cm+dn-cd}\sum _x^c (-1)^{c-x} \binom c x (\frac{q}{q-1})^{x(m-d)} \sum _y^d (-1)^{d-y} \binom d y (\frac{q}{q-1})^{y(n-c+x)}\\ =&(q-1)^{cm+dn-cd}\sum _x^c (-1)^{c-x} \binom c x (\frac{q}{q-1})^{x(m-d)} \sum _y^d (-1)^{d-y} \binom d y ((\frac{q}{q-1})^{n-c+x})^y\\ =&(q-1)^{cm+dn-cd}\sum _x^c (-1)^{c-x} \binom c x (\frac{q}{q-1})^{x(m-d)} ((\frac{q}{q-1})^{n-c+x}-1)^d \end{aligned} \] 标签:dn,map,6975,frac,cm,sum,cd,binom,GMOJ From: https://www.cnblogs.com/fydj/p/18299487/GMOJ6975