自动搬运

查看原文

来自洛谷，原作者为

	喵仔牛奶 黄昏再美终要黑夜。

搬运于2025-08-24 23:09:11，当前版本为作者最后更新于2025-01-10 07:15:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Solution

考虑如何对 $S$ 计算 $g(S)$，一种计算方式是 $g(S)$ 等于满足 $S_{i-1}\neq S_i$ 的位置 $i$ 数量再加上 $1$。

先考虑那个 $+1$，一共有 $\binom{n+m}{n}$ 个 $\tt 01$ 串 $S$，这部分贡献为 $\binom{n+m}{n}$。

接着考虑对于位置 $i$，$S_i\neq S_{i-1}$ 的方案数。$S_{i-1}S_i$ 可能是 $\tt 01$ 或 $\tt 10$，然后其它 $\lvert S\rvert-2$ 的个位置随便排，这部分贡献为 $\binom{n+m-2}{n-1}\times 2$。可以发现对于所有 $i$ 贡献都一样，所以乘上 $n+m-1$。

因此答案为

$$\binom{n+m}{n}+(n+m-1)\times\binom{n+m-2}{n-1}\times 2 $$