题解：Lovely 139
喵仔牛奶
·
·
题解
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