2020-2021 ICPC 亚洲区域赛 济南站 L.Bit Sequence @ Wings            分类 ACM
发布于 星期五, 一月 22 日, 2021 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

设$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: 被wmx hack了qaq

1 2 148 0 0

24

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

代码
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;
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch