统计构造好字符串的方案数
统计构造好字符串的方案数
题目描述
给你四个整数 low、high、zero 和 one。你从一个空字符串开始，每次操作可以选择以下两种之一（可重复任意次）：
- 在当前字符串末尾添加
'0'恰好zero次； - 在当前字符串末尾添加
'1'恰好one次。
如果最终得到的字符串长度在区间 [low, high] 内（包含端点），则称其为 好字符串。
请你返回不同好字符串的数目。由于答案可能非常大，请对结果取模 后输出。
注意：即使两个字符串内容相同，只要构造方式不同但结果一样，仍视为同一个字符串。本题统计的是不同的字符串内容，而不是构造路径。
输入格式
一行，包含四个整数：
low high zero one
其中：
输出格式
输出一个整数，表示好字符串的数量对 取模后的结果。
示例
示例 1
输入：
3 3 1 1
输出：
8
解释：
每次可以加 1 个 '0' 或 1 个 '1'，因此所有长度为 3 的二进制字符串均可构造（共 个）。
示例 2
输入：
2 3 1 2
输出：
5
解释：
合法的好字符串有：
- 长度为 2：
"00"（两次加'0'）、"11"（一次加'1'两次） - 长度为 3：
"000"（三次'0'）、"110"（先'1'×2 再'0'×1）、"011"（先'0'×1 再'1'×2）
共 5 个。