Codeforces Goodbye 2020 G. Song of the Sirens @ Wings            分类 ACM
发布于 星期三, 一月 20 日, 2021 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

给出两个字符串$s_0, t$, 其中$|s_0| \le 100, |t| \le n$. 设$s_{i+1} = s_i + t_i + s_i$, + 表示字符串连接. $q$ 个询问, 形如 k sq, $k$是整数, $sq$ 是非空字符串, 表示询问 $s_k$ 中, $sq$ 的出现次数.

$k < n \le 10^5, q \le 10^6$

题解

首先注意到, $sk$ 的长度是指数爆炸的, 所以不能完全构造出来.

但是 $sq$ 比较短, 我们可以构造出长度恰好大于等于 $sq$ 的$skk$. 注意到 $|skk| \le 2|sq| + 1$这样的话可以在 $O(2|sq|)$ 内求出 $sq$ 在 $skk$ 中出现了几次. KMP或者hash都能做.

$s_{kk+1} = skk + tkk + skk$, 会发现, $skk$已经算过了, 要计算的就是**包含$tkk$**的字符串中, $sq$ 出现的次数.

我们可以这样构造:

先取出$skk$的长度等于$|sq|-1$的后缀$suf$, 再取出长度等于$|sq|-1$的前缀$pre$, 构造$st = suf + tkk + pre$, 这样求 $sq$ 在 $st$ 中出现的次数, 就是包含 $tkk$ 的次数了.

根据上述推导, 我们能够整出一个递推式: 设$f(i)$为 $sq$ 在 $s_i$ 中出现的次数, 有

$$f(i) = 2f(i-1) + (sq \text{在当前} st \text{中出现的次数})$$

设 $g(i) = (sq \text{在算f(i)的} st \text{中出现的次数})$, 对应上式的 $st$ 那一部分的贡献.

这个递推式很简单, 类似二进制, 我们可以直接写出 $f(k)$ 的表达式

$$f(k) = 2^{k-kk}f(kk) + \sum_{i=kk+1}^k 2^{k-i}g(i)$$

我们已经算过 $f(kk)$ 了, 现在要求的是后面一个式子.

可以发现, 当$|skk| \ge |sq|$ 时, 在$t_i, i>kk$旁边的永远都是$suf$和$pre$. 证明简单, 可参考官方题解.

所以, 我们可以预处理一下 $skk + T + skk$, 其中 $T$ 取遍字符集, 即 $26$ 个小写字母. 当 $t_i = c$ 时, 我们就加上 $2^{k-i} \cdot (sq \text{在} skk + c + skk \text{中出现次数})$.

那么, 可以这样转化贡献:

我们遍历这$26$个字母, 当$t_i = c$时加上上述贡献, $t_i \ne c$时不加贡献. 结合下图理解一下:

贡献转化示意图

由于 $t_i$ 取相同值是, $oc_c$ 是相同的, 所以我们甚至可以把他提出来, 那么剩下的部分就是一堆二的次幂的和, 这些和就可以看作 $oc_c$ 的贡献.

我们可以预处理出这些和, 那么就可以从遍历$26$个字母, 求 $oc_{c} \cdot \text{贡献}$ 加入答案.

这一部分的共贡献可以用类似哈希(或者说p进制)的做法求, 只不过要对每一个字符都做一遍, 得到 $26$ 个 sum[i], 然后分别对应地算 $sum[k] - sum[kk]$就是这些贡献了. 乘到$oc_{c}$上就是对答案的贡献.

于是每一次询问就可以在$O(26)$内算出答案了.

还要注意可能 $|sq| > |sk|$, 这样我们的算法做出来会有 $kk > k$, 特判一下这种情况答案是$0$.

有点绕, 写完还是没有特别清楚这个转化过程, 还需要多看多想.

总复杂度$O(q)$

代码
const int P = 1e9 + 7;

const int MAXN = 1e5+10;
const int MAXM = 1e6+10;

int Plus(LL a, LL b) {
	return a + b >= P ? (a + b) % P : a + b;
}
int Minus(LL a, LL b) {
	return Plus(a, P-b);
}
int Mult(LL a, LL b) {
	return a * b >= P ? a * b % P : a * b;
}

int n, q, k, ans = 0, oc[30];

char s0[110], t[MAXN], sq[MAXM];

string get_sw(int len, int &cur, int &cur_len) {
	cur_len = strlen(s0);
	string s_cur = s0;
	while (cur_len < len) {
		s_cur = s_cur + t[cur++] + s_cur;
		cur_len = cur_len * 2 + 1;
	}
	return s_cur;
}

int f[MAXM];
void kmp_init(int len) {
	f[0] = f[1] = 0;
	int j = 0;
	for (int i = 1; i < len; i++) {
		j = f[i];
		while (j && sq[i] != sq[j])
			j = f[j];
		f[i+1] = sq[i] == sq[j] ? j+1 : 0;
	}
}

int kmp(string T, int len2) {
	int cnt = 0, j = 0, len1 = T.length();
	for (int i = 0; i < len1; i++) {
		while (j && T[i] != sq[j])
			j = f[j];
		if (T[i] == sq[j])
			j++;
		if (j == len2)
			cnt++;
	}
	return cnt;
}

int pw[MAXN], sum[30][MAXN];
void init() {
	pw[0] = 1;
	for (int i = 1; i <= n; i++)
		pw[i] = Mult(pw[i-1], 2);
	for (char c = 'a'; c <= 'z'; c++) {
		for (int i = 0; i < n; i++)
			sum[c-'a'][i+1] = Plus(Mult(sum[c-'a'][i], 2), t[i] == c);
	}
}

int main() {
	scanf("%d%d%s%s", &n, &q, s0, t);
	init();
	while (q--) {
		scanf("%d%s", &k, sq);
		int sq_len = strlen(sq);
		kmp_init(sq_len);
		int kk = 0, sw_len = 0;
		string sw = get_sw(sq_len, kk, sw_len);
		int occ = kmp(sw, sq_len);
		if (k >= kk) {
			ans = Mult(occ, pw[k-kk]);
			for (char c = 'a'; c <= 'z'; c++) {
				string st = sw.substr(sw_len - sq_len + 1, sq_len-1) + c + sw.substr(0, sq_len-1);
				oc[c-'a'] = kmp(st, sq_len);
				ans = Plus(ans, Mult(oc[c-'a'], Minus(sum[c-'a'][k], Mult(sum[c-'a'][kk], pw[k-kk]))));
			}
		}
		else
			ans = 0;
		printf("%d\n", ans);
	}
	return 0;
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

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

个人简介

我叫 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. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

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

运动

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

音乐

  • 吉他
  • 词曲
  • 流行

玩具

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

追星

  • VAE
  • Benedict Cumberbatch