设$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{所有交界处的贡献}$
交界一共有四种情况:
- $A A'$
- $A’ A$
- $A’ A'$
- $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
这里就是因为取了不应该取的后缀, 前面多了一个$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;
}
|