P11655 题解

getchar_unlocked · 2025-02-09 22:52:03 · 题解

题目传送门

思路

组合数问题。

对于一个 \texttt{01} 串 S，具有 C_{n+m}^n 种组合方案。然后若两个相邻的字符不同，颜色段段数需增加 1。去掉这一位后剩余 C_{n+m-2}^{n-1} 种组合方案。最后乘上两个字符相同情况 n+m-1 即可。

预处理阶乘和逆元，将单次询问的复杂度降为 \mathcal{O}(\log(n+m))。最终时间复杂度为 \mathcal{O}(n+m+T\log(n+m))。

注意事项

• 不开 long long 见祖宗。
• 随时取模。