P11566

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

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

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

其中 $\dim(R)$ 显然是 $(n-a+1)(m-b+1)$，$\dim(B)$ 同理。难点在于如何算 $\dim(R\cap B)$。不妨先就一维的问题进行讨论，将问题使用在 $\mathbb{F}_2$ 意义下的生成函数刻画（这一手法在 CF1698G 中也可见得）：令 $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)$ 就是

当然得特判减成 $<0$ 的情况。复杂度瓶颈在于快速幂/求 $\gcd$ 为 $\mathcal{O}(T\log{V})$。