给你一个用二进制表示的区间[A,B][A,B]

求这个区间内的数在二进制的表示下有aa个00，bb个01，cc个10，dd个11的有多少个

1≤A≤B≤21000001\le A \le B\le 2^{100000}

CF1045H

Solution

首先考虑没有区间[A,B][A,B]限制的时候怎么做

不难发现，序列是由若干段连续的00或11交替组成的

总的11的个数为b+d+1b+d+1，最后我们要把它们分成b+1b+1个连续段。根据隔板法有(b+db)\binom{b+d}{b}种方案，00的情况同理

所以答案就是(b+db)∗(a+c−1c−1)\binom{b+d}{b}*\binom{a+c-1}{c-1}

接着考虑如何把多算的部分减掉

利用类似数位dp的思想，从高位往低位考虑，枚举在哪一位上第一次超过限制，那么后面就能随便填，又转化成上面那个式子了

Summary

又是一道并不难的组合计数题。考试的时候一直在想如何优化数位dp，没发现能直接通过组合数计算答案

虽然发现了序列由若干段0101交替组成，但没有很好地利用这个性质与已知信息的联系，所以才没想到

以后的组合计数题都要逼着自己去想，去推，先独立思考，否则不可能有提高

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

inline void proc_status()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) <<endl;
}

template <typename T> T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int Maxn = 200000 + 100, Mod = 1000000007;

int N, A[Maxn], M, B[Maxn], a, b, c, d;
int fac[Maxn], ifac[Maxn];
char S[Maxn];

inline void Add (int &a, int b) { a += b; if (a >= Mod) a -= Mod; }

inline int Pow (int a, int b)
{
	int ans = 1;
	for (int i = b; i; i >>= 1, a = 1ll * a * a % Mod) if (i & 1) ans = 1ll * ans * a % Mod;
	return ans;
}

inline int C (int n, int m) { return 1ll * fac[n] * ifac[m] % Mod * ifac[n - m] % Mod; }

inline int calc (int n, int m) 
{ 
	if (n < 0 || m < 0) return 0;
	if (!m) return !n;
	return C(n + m - 1, m - 1); 
}

inline int solve ()
{
	if (a + b + c + d > N - 1) return 0;
	int ans = 1ll * calc (d, b + 1) * calc (a, c) % Mod;
	if (a + b + c + d < N - 1) return ans;

	int aa = a, bb = b, cc = c, dd = d;
	for (int i = N - 1; i >= 1; --i)
	{
		if (A[i] == 1)
		{
/**/		if (A[i + 1] == 1) --dd;
			else --bb;
			continue;
		}

		if (A[i + 1] == 1) Add (ans, Mod - 1ll * calc (dd - 1, bb + 1) * calc(aa, cc) % Mod);
		else Add (ans, Mod - 1ll * calc (dd, bb) * calc(aa, cc) % Mod);

		if (A[i + 1] == 1) --cc; else --aa;
	}
	return ans;
}

inline void Solve ()
{
	if (b + 1 < c || c < b) { cout<<0<<endl; return ; }
	--A[1];
	for (int i = 1; i < N; ++i) if (A[i] < 0) A[i] = 1, --A[i + 1];
	if (!A[N]) --N;
	int ans = Mod - solve();
	swap(N, M), swap(A, B);
	printf("%d\n", (ans + solve()) % Mod);
}

inline void Input ()
{
	scanf("%s", S + 1); N = strlen(S + 1);
	for (int i = 1; i <= N; ++i) A[i] = S[N - i + 1] - '0';
	scanf("%s", S + 1); M = strlen(S + 1);
	for (int i = 1; i <= M; ++i) B[i] = S[M - i + 1] - '0';
	a = read<int>(), b = read<int>(), c = read<int>(), d = read<int>();
}

inline void Init (int maxn)
{
	fac[0] = 1;
	for (int i = 1; i <= maxn; ++i) fac[i] = 1ll * fac[i - 1] * i % Mod;
	ifac[maxn] = Pow(fac[maxn], Mod - 2);
	for (int i = maxn - 1; i >= 0; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % Mod;
}

int main()
{
#ifdef hk_cnyali
	freopen("H.in", "r", stdin);
	freopen("H.out", "w", stdout);
#endif
	Init(2e5);
	Input();
	Solve();
	return 0;
}