二进制数

题目链接：YBT2023寒假Day14 B

题目大意

问你 [A,B] 之间有多少个整数，满足它二进制表示下（不要前导 0）子串 00,01,10,11 个数分别是 a,b,c,d。
其中 A,B<=2^{100000}，a+b+c+d<=100000

思路

首先转成求 \([1,x]\) 的答案。
然后考虑数位 DP，考虑当你发现可以任取了之后，有多少方案。

那么我们假设任取的时候，你还剩下 \(a,b,c,d\) 个 \(00,01,10,11\) 要选。
然后因为你要出现任取，那这一位一定上界是 \(1\) 你选了 \(0\)，所以肯定是从 \(0\) 开始。
然后你会发现，你在 \(0\) 的时候只能选 \(00,01\)，分别会走到 \(0,1\)，\(1\) 的时候只能走 \(10,11\)，分别会走到 \(0,1\)，有点类似矩阵的转移。（矩阵快速幂一下好像也行？）
还有一个方法是观察到最后答案会形如：
\(0...01...10...0......\)
这样的，那会发现 \(00,11\) 都可以说是插入在 \(010101...\) 之中的。
那根据 \(b,c\) 的数量，我们可以确定这个 \(01\) 交替串的长度以及最后的结尾。
然后 \(01\) 之间可以放 \(00\)，\(10\) 之间可以放 \(11\)，如果最后一个 \(1\) 后面可以放 \(11\)，如果最后一个是 \(0\) 后面可以放 \(00\)。
那就是这些位置里面可以放东西，那就是若干个东西放入若干个桶中，直接上插板法即可。

要注意如果一直不能任取最后得到的是 \(x\)，要单独判一次（别问我为啥单独讲，寄）

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define mo 1000000007

using namespace std;

const int N = 4e5 + 100;
int A[N], B[N], a, b, c, d, an, bn;
ll jc[N], inv[N], invs[N];
char s[N];

ll C(int n, int m) {
	if (n < 0 || m < 0 || n < m) return 0;
	return jc[n] * invs[m] % mo * invs[n - m] % mo;
}

void dec1() {
	int now = 1;
	while (!A[now]) now++;
	A[now] = 0;
	for (int i = now - 1; i >= 1; i--) A[i] = 1;
	if (now == an) an--;
}

ll slove(int *F, int n) {
	if (a + b + c + d + 1 == 1) {
		if (n == 1) return F[1] + 1;
		return 2;
	}
	int aa = a, bb = b, cc = c, dd = d; ll ans = 0;
	for (int i = n - 1; i >= 1; i--) {
		if (c > b + 1 || b > c) continue;
		if (a + b + c + d + 1 != i) continue;
//		if (b == c) {
//			//d:b+1 λÖÃ
//			//a:c λÖà 
//		}
//		if (b + 1 == c) {
//			//d:b+1 λÖÃ
//			//a:c λÖà 
//		}
		(ans += C(b + 1 + d - 1, b + 1 - 1) * C(c + a - 1, c - 1) % mo) %= mo;
	}
	for (int i = n - 1; i >= 1; i--) {
		if (!F[i]) {
			if (F[i + 1]) cc--;
				else aa--;
			continue;
		}
		
		if (F[i + 1]) cc--;
			else aa--;
		if (aa + bb + cc + dd + 1 == i)	{
			if (cc == bb || cc + 1 == bb) {
				(ans += C(cc + 1 + aa - 1, cc + 1 - 1) * C(bb + dd - 1, bb - 1) % mo) %= mo;
			}
		}
		if (F[i + 1]) cc++;
			else aa++;
		
		if (F[i + 1]) dd--;
			else bb--;
	}
	if (!aa && !bb && !cc && !dd) (ans += 1) %= mo;//记得最后如果所有相等也要比较
	return ans;
}

int main() {
//	freopen("sjs.txt", "r", stdin);
//	freopen("my.txt", "w", stdout);
	freopen("binary.in", "r", stdin);
	freopen("binary.out", "w", stdout);
	
	jc[0] = 1; for (int i = 1; i < N; i++) jc[i] = jc[i - 1] * i % mo;
	inv[0] = inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	invs[0] = 1; for (int i = 1; i < N; i++) invs[i] = invs[i - 1] * inv[i] % mo;
	 
	scanf("%s", s + 1); an = strlen(s + 1);
	for (int i = 1; i <= an; i++) A[i] = s[i] - '0'; reverse(A + 1, A + an + 1);
	scanf("%s", s + 1); bn = strlen(s + 1);
	for (int i = 1; i <= bn; i++) B[i] = s[i] - '0'; reverse(B + 1, B + bn + 1);
	scanf("%d %d %d %d", &a, &b, &c, &d);
	
	dec1();
	printf("%lld", (slove(B, bn) - slove(A, an) + mo) % mo);
	
	return 0;
}