Self-exploration
题意翻译
求在$[l,r]$区间内有多少数满足在二进制下:
- 子串$00$的个数为$C00$。
- 子串$01$的个数为$C01$。
- 子串$10$的个数为$C10$。
- 子串$11$的个数为$C11$。
答案对$10^9+7$取模。
$\large l,r≤2^{100 \ 000}$
题目描述
Being bored of exploring the Moon over and over again Wall-B decided to explore something he is made of — binary numbers. He took a binary number and decided to count how many times different substrings of length two appeared. He stored those values in $ c_{00} $ , $ c_{01} $ , $ c_{10} $ and $ c_{11} $ , representing how many times substrings 00, 01, 10 and 11 appear in the number respectively. For example:
$ 10111100 \rightarrow c_{00} = 1, \ c_{01} = 1,\ c_{10} = 2,\ c_{11} = 3 $
$ 10000 \rightarrow c_{00} = 3,\ c_{01} = 0,\ c_{10} = 1,\ c_{11} = 0 $
$ 10101001 \rightarrow c_{00} = 1,\ c_{01} = 3,\ c_{10} = 3,\ c_{11} = 0 $
$ 1 \rightarrow c_{00} = 0,\ c_{01} = 0,\ c_{10} = 0,\ c_{11} = 0 $
Wall-B noticed that there can be multiple binary numbers satisfying the same $ c_{00} $ , $ c_{01} $ , $ c_{10} $ and $ c_{11} $ constraints. Because of that he wanted to count how many binary numbers satisfy the constraints $ c_{xy} $ given the interval $ [A, B] $ . Unfortunately, his processing power wasn't strong enough to handle large intervals he was curious about. Can you help him? Since this number can be large print it modulo $ 10^9 + 7 $ .
输入输出格式
输入格式
First two lines contain two positive binary numbers $ A $ and $ B $ ( $ 1 \leq A \leq B < 2^{100\,000} $ ), representing the start and the end of the interval respectively. Binary numbers $ A $ and $ B $ have no leading zeroes.
Next four lines contain decimal numbers $ c_{00} $ , $ c_{01} $ , $ c_{10} $ and $ c_{11} $ ( $ 0 \leq c_{00}, c_{01}, c_{10}, c_{11} \leq 100\,000 $ ) representing the count of two-digit substrings 00, 01, 10 and 11 respectively.
输出格式
Output one integer number representing how many binary numbers in the interval $ [A, B] $ satisfy the constraints mod $ 10^9 + 7 $ .
输入输出样例
输入样例 #1
10
1001
0
0
1
1
输出样例 #1
1
输入样例 #2
10
10001
1
2
3
4
输出样例 #2
0
说明
Example 1: The binary numbers in the interval $ [10,1001] $ are $ 10,11,100,101,110,111,1000,1001 $ . Only number 110 satisfies the constraints: $ c_{00} = 0, c_{01} = 0, c_{10} = 1, c_{11} = 1 $ .
Example 2: No number in the interval satisfies the constraints