题解

思路

设 $N=n+m$。当 $N=0$ 时，答案为 $0$。以下只讨论非空字符串。

一个非空 01 串的极长颜色段数，等于 $1$ 加上相邻字符不同的位置数。因此可以分别统计所有字符串各自贡献的第一个颜色段，以及所有相邻异色位置的贡献。

恰含 $n$ 个 0 的长度为 $N$ 的字符串有 $\binom Nn$ 个。固定一个相邻位置，并指定这两位为 01 或 10，剩余 $N-2$ 位需要放置 $n-1$ 个 0，共有 $2\binom{N-2}{n-1}$ 种。相邻位置共有 $N-1$ 个，所以

当 $n=0$ 或 $m=0$ 时，第二项为 $0$，公式给出唯一单色串的一个颜色段。

做法

先读入全部询问，找到最大的 $n+m$。预处理阶乘与逆阶乘，并用费马小定理求最高阶乘的逆元，再递推得到其余逆阶乘。每个组合数可在常数时间内计算，将其代入上式即可。

正确性证明

每个非空字符串恰好为基础项贡献一次，因此基础项总和是 $\binom Nn$。任取一个相邻位置，形成 01 或 10 后，其余位置有 $\binom{N-2}{n-1}$ 种选择；两个方向共计 $2\binom{N-2}{n-1}$。对全部 $N-1$ 个相邻位置求和，得到全部字符串的相邻变化总数。两部分相加正好等于所有字符串的极长颜色段数之和，所以算法正确。

复杂度

设所有询问中的最大 $n+m$ 为 $M$。时间复杂度为 $O(M+T)$，空间复杂度为 $O(M+T)$。