P11566

· · 题解

一个比官方题解好理解得多的做法！！！

需要一定线性代数/生成函数基础。

问题其实就是给定线性空间 R,B 求 \dim(R+B)（注意这里是和而非并）。使用线性代数维数公式，得 \dim(R+B)=\dim(R)+\dim(B)-\dim(R\cap B)。

::::info[Proof]

设 \dim(R)=n,\dim(B)=m,\dim(R\cap B)=k。取 R\cap B 的一组基 \pmb{\alpha}_{1\sim k}，分别扩展成 R/B 的基为 \pmb{\alpha}_{1\sim k},\pmb{\beta}_{1\sim n-k} 和 \pmb{\alpha}_{1\sim k},\pmb{\gamma}_{1\sim m-k}。

问题即为，说明 \pmb{\alpha}_{1\sim k},\pmb{\beta}_{1\sim n-k},\pmb{\gamma}_{1\sim m-k} 这些向量线性无关。反证，若：

:::: 其中 $\dim(R)$ 显然是 $(n-a+1)(m-b+1)$，$\dim(B)$ 同理。难点在于如何算 $\dim(R\cap B)$。不妨先就一维的问题进行讨论，将问题使用在 $\mathbb{F}_2$ 意义下的生成函数刻画（这一手法在 [CF1698G](https://codeforces.com/problemset/problem/1698/G) 中也可见得）：令 $F_a(x)=\sum\limits_{0\le i<a}x^i$，$F_c(x)$ 同理。向量 $v\in R$ 当且仅当有 $P(x)(\deg{P}\le n-a)$ 满足 $v(x)=P(x)F_a(x)$；向量 $v\in B$ 当且仅当有 $Q(x)(\deg{Q}\le n-c)$ 满足 $v(x)=Q(x)F_c(x)$。 若 $v\in R\cap B$ 则有 $P(x)F_a(x)=Q(x)F_c(x)$，此处必须有 $P(x)F_a(x)$ 是 $F_c(x)$ 的倍数，即 $P(x)$ 是 $\frac{F_c(x)}{\gcd(F_a(x),F_c(x))}$ 的倍数。$\gcd(F_a(x),F_c(x))$ 是什么？更损相减一下，就是 $\gcd(x^c\cdot F_{a-c}(x),F_c(x))(a>c)=\gcd(F_{a-c}(x),F_c(x))$，从而 $\gcd(F_a(x),F_c(x))=F_{\gcd(a,c)}(x)$。 若 $P(x)=G(x)\frac{F_c(x)}{\gcd(F_a(x),F_c(x))}$，则 $G(x)$ 仅需 $\deg{G}\le n-a-c+\gcd(a,c)$（另一边 $\deg{Q}\le n-c$ 的限制推出来是一样的），任意的 $G(x)$ 都可决定 $v$，而 $\deg{G}$ 可取遍 $0\sim n-a-c+\gcd(a,c)$，故 $\dim(R\cap B)$ 即为该值 $+1$。 对于二维的问题，可以直接列二维生成函数，你会发现运算过程中两维是完全对立的，换句话说，$\dim(B\cap R)$ 就是 $$ (n-a-c+\gcd(a,c)+1)(m-b-d+\gcd(b,d)+1) $$ 当然得特判减成 $<0$ 的情况。复杂度瓶颈在于快速幂/求 $\gcd$ 为 $\mathcal{O}(T\log{V})$。