2020-2021 ICPC 亚洲区域赛 济南站 L.Bit Sequence

警告
本文最后更新于 2021-01-26,文中内容可能已过时。

设$f(x)$为$x$二进制下$1$的个数. 给出长度为$m$的$01$序列$a$, 给出$L$, 求有多少个$x \in [0, L]$, 满足$f(x + i) \mod 2 = a_i$

$1 \le m \le 100, 0 \le L \le 10^{18}$

设$g(i) = f(i) \mod 2$

我们把$g(i)$求出$[0, L+m]$个, 排成一排, 然后就类似于字符串匹配一样统计个数.

注意到$L$很大, 我们没办法把这个序列全部求出来. 所以这个序列一定有规律.

注意到, 当$i \in [2^{k-1}, 2^k)$时, 有$f(i + 2^k) = f(i) + 1$, 也就是相当于$i$的二进制下的第$k$位从$0$变成$1$, 所以有$g(i + 2^k) = g(i) \oplus 1$. 这样, 我们就发现了序列$g$的构造方式:

第一个是0, 然后把当前序列取反, 拼在后面. 如下:

0
01
0110
01101001
0110100110010110
...

还注意到 $m$ 很小, 只有$100$, 而$2^7 = 128$. 所以我们可以先构造出$g$的前$128$位, 更大的数一定会包含这个序列多次. 用$h(i)$表示$g$的前$2^i$位的序列, $h’(i)$表示$h(i)$每一位取反的序列.

很容易知道$h(8) = h(7) + h’(7)$. 为方便, 令$A = h(7), A’ = h’(7)$.

$h(i)$长这样 $AA’ A’ AA’ AAA’ \dots$

再令$dp(X)$为$a$在序列$X$中出现的次数, 那么有:

$dp(h(i)) = dp(h(i-1)) + dp(h’(i-1)) + a\text{在}h(i-1)\text{和}h’(i-1)\text{交界部分出现的次数}, i \ge 8$

这个式子可以直接推到底, 变成$dp(h(i)) = 2^{i-8} (dp(A) + dp(A’)) + \text{所有交界处的贡献}$

交界一共有四种情况:

  1. $A A'$
  2. $A’ A$
  3. $A’ A'$
  4. $AA$

设$P$为$A$的长度为$m-1$的前缀, $S$为$A$的长度为$m-1$的后缀, $P’, S’$为取反.

那么实际上我们求出$a$在$SP$中出现的次数, 就是$AA$交界处的贡献了. 而且取$m-1$, 正好算出$SP$的所有次数不会在$A$或者$A’$计算到.

$dp(SP)$等可以求出.

那么求所有交界处的贡献无非就是求$dp(SP)$的系数.

设$F(i, 0/1/2/3)$分别为序列$h(i)$中, $SP’, S’ P, S’ P’, SP$的出现次数.

$h(i)$的前半段和$h(i-1)$一样, 后半段是$h’(i-1)$, 所以首先有:

$$F(i, 1) = F(i, 0) = F(i-1, 0) + F(i-1, 1)$$ $$F(i, 2) = F(i, 3) = F(i-1, 2) + F(i-1, 3)$$

还差一个$h(i)$和$h’(i)$交界处的.

$h(i)$第一个一定是$A$, 所以$h’(i)$的第一个一定是$A’$. 可以发现, $h(i)$的最后一个和$i$有关, $i=8$时, 是$A’$, $i = 9$时是$A$, $i=10$时是$A’$, $\dots$

易得, $i$为偶数时, $F(i, 0)$多加一下, $i$为奇数时, $F(i, 2)$多加一下.

再设一个$G(i, 0/1/2/3) = F(i, 1/0/3/2)$, 表示$h’(i)$中四种交界的出现次数, 待会要用到.

我们把$L$进行二进制拆分, 从大到小枚举位置.

假如第$11, 9, 8$位都是$1$, 那么序列前面应该是$h(11)h’(9)h(8)$(因为取反), 用 cnt 记录这个位置是否需要取反.

同时需要注意, $h(i)h(j)$ 交界处也要算上, 也是有四种情况, 讨论一下. 不需要推导, 只需要手写一些小数据, 然后看每个情况就行.

我们只做到了序列$g$的前$\sum_{i \ge 8} k_i \cdot 2^i$($k_i$是$L$二进制下第$i$位的数字), 还有后面一堆没算. 设后面一堆为$R$, $R$一定是$h(8)$或者$h’(8)$的前缀(具体是哪一个还是要讨论). 而已经算过的序列的最后是$A$或者$A’$(具体是哪一个依然需要讨论), 把前面的长度为$m-1$的后缀和$R$拼起来, 暴力求一下, 就解决了$R$以及做过的序列和$R$交界处的贡献.

UPD: 注意, 如果第$8$位及以上都没有$1$的话, 就不用取后缀了.

当然$L+m$不足$128$的时候暴力就行.

复杂度$O(m^2 + \log L)$

UPD: 被王老师 hack 了 qaq

输入
1
2 148
0 0
输出
24

这里就是因为取了不应该取的后缀, 前面多了一个$0$, 又由于第一位是$0$, 所以多了一个$00$

  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
119
120
const int MAXN = 70;
const int MAXM = 1e3+10;

int t, m;
LL f[10][MAXN][10], a[MAXM], occ[10], ocsum;
LL L, ans = 0;
VI A, B, C[10], D, E;

VI flip(VI X) {
	VI res;
	for (auto x : X)
		res.push_back(x^1);
	return res;
}

LL calc(VI X) {
	LL res = 0;
	for (int i = 0; i < (int)X.size() - m + 1; i++) {
		int flag = 1;
		for (int j = 0; j < m; j++) {
			if (X[i+j] != a[j]) {
				flag = 0;
				break;
			}
		}
		res += flag;
	}
	return res;
}

int main() {
	scanf("%d", &t);
	f[0][8][0] = 1;
	for (int i = 9; i <= 63; i++) {
		for (int j = 0; j < 4; j++)
			f[0][i][j] = f[0][i-1][j] + f[0][i-1][j^1];
		f[0][i][i&1 ? 2 : 0]++;
	}
	for (int i = 8; i <= 63; i++)
		for (int j = 0; j < 4; j++)
			f[1][i][j] = f[0][i][j^1];
	A.push_back(0);
	for (int i = 1; i <= 7; i++) {
		B = flip(A);
		A.insert(A.end(), B.begin(), B.end());
	}
	B = flip(A);
	D = A;
	D.insert(D.end(), B.begin(), B.end());
	E = flip(D);
	while (t--) {
		scanf("%d%lld", &m, &L);
		L += m;
		for (int i = 0; i < m; i++)
			scanf("%d", a + i);
		ans = 0;
		if (L <= 128) {
			VI v;
			for (int i = 0; i < L; i++)
				v.push_back(A[i]);
			ans = calc(v);
		}
		else {
			ocsum = calc(A) + calc(B);
			for (int i = 0; i < 4; i++)
				C[i].clear();

			for (int i = 1; i <= m-1; i++)
				C[0].push_back(A[128-i]);
			reverse(C[0].begin(), C[0].end());
			for (int i = 0; i < m-1; i++)
				C[0].push_back(B[i]);
			C[1] = flip(C[0]);

			for (int i = 1; i <= m-1; i++)
				C[2].push_back(B[128-i]);
			reverse(C[2].begin(), C[2].end());
			for (int i = 0; i < m-1; i++)
				C[2].push_back(B[i]);
			C[3] = flip(C[2]);

			for (int i = 0; i < 4; i++)
				occ[i] = calc(C[i]);
			int cnt = 0, last = -1;
			for (int i = 63; i >= 8; i--) {
				if ((1ll<<i) & L) {
					ans += ocsum * (1ll << (i - 8));
					for (int j = 0; j < 4; j++) {
						ans += occ[j] * f[cnt&1][i][j];

					}
					if (cnt) {
						if (cnt&1 && last^(cnt&1))
							ans += occ[2];
						else if (cnt&1 && last^(cnt&1)^1)
							ans += occ[0];
						else if ((cnt&1)^1 && last^(cnt&1))
							ans += occ[1];
						else
							ans += occ[3];
					}
					cnt++;
					last = i&1;
				}
			}
			VI &X = (cnt&1)^last ? B : A, &Y = cnt&1 ? E : D;
			int ret = (L & ((1ll << 8) - 1));
			VI Z;
			if (cnt)	// UPD 前面没有, 不用取后缀
				for (int i = 1; i <= m-1; i++)
					Z.push_back(X[128-i]);
			reverse(Z.begin(), Z.end());
			for (int i = 0; i < ret; i++)
				Z.push_back(Y[i]);
			ans += calc(Z);
		}
		printf("%lld\n", ans);
	}
	return 0;
}