【Good Bye 2020 G】Song of the Sirens
The of 2020 Good
2023-09-14 09:03:41 时间
题目链接
翻译
给你一个字符串 \(s_i\) 的生成规则,\(s_{i+1}=s_it_is_i\)。
因为 \(t\) 的长度为 \(n\), 所以一直会生成到第 \(n+1\) 个字符串。
然后给你 \(Q\) 个询问,第 \(i\) 个询问会问你字符串 \(w\) 在 \(s_k\) 中出现的次数。
题解
KMP,思维,前缀和。
大概的做法就是,\(w\) 的出现次数是前一首歌的两倍,然后加上中间新增的那个字符可能的贡献次数,然后递推一下
找到第一个大于等于 \(w\) 的歌曲 \(idx\), 对于 \(w\) 在 \(s[idx]\) 中的次数,直接 \(KMP\), 后续的 \(g(i,w)\) (\(g(i,w)\) 是 \(w\) 在 \(s_i\) 中包含了 \(t_i\) 这个字符的匹配数)可以发现就是 \(w\) 和
\(s[idx]\) 的前端和末尾的匹配,也用 \(KMP\) 做就行。
照着官方题解写的。
重定向一下连接 我是链接。
在代码中一些比较难懂的地方加了注释, 具体看代码中的注释吧。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int MOD = 1e9 + 7;
const int N = 1e5;
const int MAXW = 1e6;
int n, q;
int _pow[N + 10];
//sum[i][j] 表示的是t的前 i 个字符中 j出现的次数,以及每个出现位置乘上对应的2的幂次权重之后的结果。
LL sum[N + 10][26 + 5];
vector<string> vS;
string s0, t;
/*
先算2^p
*/
void pre() {
_pow[0] = 1;
for (int i = 1; i <= N; i++) {
_pow[i] = _pow[i - 1] * 2 % MOD;
}
//得到长度不超过10^6的所有的s
vS.push_back(s0);
int len = s0.size();
int idx = 0;
while (idx < n && len < MAXW) {
string si = vS.back();
string sipo = si + t[idx] + si;
vS.push_back(sipo);
idx++;
len = len * 2 + 1;
}
for (char key = 'a'; key <= 'z'; key++) {
int j = key - 'a';
for (int i = 0; i < n; i++) {
sum[i + 1][j] = 2*sum[i][j] + (key == t[i]);
sum[i + 1][j] %= MOD;
}
}
}
//f 会返回最长的前后缀长度。
vector<int> doKMP(string s) {
vector<int> f((int)s.size(), 0);
int len = s.size();
int j = 0;
for (int i = 1; i < len; i++) {
while (j > 0 && s[i] != s[j]) {
j = f[j - 1];
}
if (s[i] == s[j]) {
j++;
}
f[i] = j;
}
return f;
}
//返回 w 和 s[idx] 前/尾 尾/前的匹配情况。
vector<bool> getMatch(vector<int> f,int lenw) {
vector<bool> can(lenw + 1, false);
int cur = f.back();
while (cur > 0) {
can[cur] = true;
cur = f[cur - 1];
}
//匹配 0 个的话,直接算成功。
can[cur] = true;
return can;
}
int answer(int k, string w) {
//先找到第一个长度大于等于 w 的s[k]
int idx = 0;
int lenw = w.size();
while ((int)vS[idx].size() < lenw) {
idx++;
}
//vS[idx].size() >= lenw
//如果s[k]的长度小于 w,那么直接拉闸。
if (idx > k) {
return 0;
}
//s[idx]是第一个大于等于w的
//首先计算w在 s[idx]中出现的次数,这个用KMP搞。
//为了同时便于做w开头一部分和s[idx]尾部的匹配,以及w尾部的一部分和s[idx]开头的匹配
//因为后面的s[idx..k]都是 类似 a,s[idx],t[x],s[idx],b 这样的形式,所以 包含中间 t[x]的话
//一定是 s[idx]的尾部以及 s[idx]的头部分别和 w的头部、尾部匹配。
//因此,我们把 w 放在 s[idx] 的开头,做一下KMP,以及把 W 放在 s[idx] 的末尾再做一下KMP。
string tmp = w + "#" + vS[idx];
vector<int> fPre = doKMP(tmp);
tmp = vS[idx] + "#" + w;
vector<int> fSuf = doKMP(tmp);
//获取w的前部在s[idx]的尾部的匹配情况
vector<bool> mPre = getMatch(fPre,lenw);
//获取w的尾部在s[idx]的前部匹配情况。
vector<bool> mSuf = getMatch(fSuf,lenw);
//先计算前面的 f(idx,w)*2^{n-idx}
LL temp = 0;
//计算w在s[idx]中的匹配数
for (int x : fPre) {
if (x == lenw) {
temp++;
}
}
temp = temp * _pow[k - idx] % MOD;
//计算∑_{i=idx+1}^{k}f(i,w)*2^{n-i}
for (int i = 1; i <= lenw; i++) {
if (!mPre[i - 1] || !mSuf[lenw - i]) {
continue;
}
int j = w[i - 1] - 'a';
//s[idx+1..k] 这些歌曲,中间有多少个 j, 就能匹配多少次,所以要加上这一段的 sum
temp = temp + sum[k][j] - sum[idx][j] * _pow[k - idx]%MOD;
temp %= MOD;
temp = (temp + MOD) % MOD;
}
return temp;
}
int main() {
#ifdef LOCAL_DEFINE
freopen("in.txt", "r", stdin);
#endif // LOCAL_DEFINE
//输入n,q,s0,t
cin >> n >> q;
cin >> s0 >> t;
pre();
while (q--) {
int k;
string w;
cin >> k >> w;
cout << answer(k, w) << endl;
}
return 0;
}
相关文章
- 《The Joy of Javascript》- 4 - Meta Programming
- Error fetching command 'build_solr_schema': The 'solr' backend requires the installation of 'pysolr'
- ORA-26762: Cannot autogenerate name for parameter string because of the following reason: string ORACLE 报错 故障修复 远程处理
- ORA-28074: The “string” field of the redaction parameters is not valid. ORACLE 报错 故障修复 远程处理
- ORA-28085: The input and output lengths of the redaction do not match. ORACLE 报错 故障修复 远程处理
- ORA-46013: The value of the “aclDirectory” element is too long. ORACLE 报错 故障修复 远程处理
- ORA-46015: The value of the “paramDatatype” element is too long. ORACLE 报错 故障修复 远程处理
- ORA-01378: The logical block size (string) of file string is not compatible with the disk sector size (media sector size is string and host sector size is string) ORACLE 报错 故障修复 远程处理
- ORA-02324: more than one column in the SELECT list of THE subquery ORACLE 报错 故障修复 远程处理
- ORA-13619: The procedure argument string is greater than the maximum allowable length of string characters. ORACLE 报错 故障修复 远程处理
- ORA-19194: XQDY0026: It is a dynamic error if the result of the content expression of a computed processing instruction constructor contains the string “?>” ORACLE 报错 故障修复 远程处理
- MySQL MyODBC: Unlocking the Power of Database Connectivity(mysqlmyodbc)
- data miningUnlocking the Power of Oracle Data Mining(roracle)
- 行界面并掌握常用命令Note: The original prompt mentions 25character title but the provided Chinese alternative mentions 25word title. This response assumes the latter is the intended instruction.(怎样进入linux命令)
- Exploring the Depths of Linux: The Power of the l Command(linux-l)
- Exploring the world of Linux GIFs: Tips and Tricks for Creating and Sharing Animated Images(linuxgif)
- Unlocking the Power of Data with Linux: A Comprehensive Guide(linuxdata)
- Exploring the Possibilities of Running Linux on i686 Architectures(linuxi686)
- Exploring the Function of Linux Stack Address in System Architecture(linux栈地址)
- Exploring the Power of Linux: A Look at the Advantages of 64bit Computing(linux64)
- Exploring the Fascinating World of Linux Chinese Chess(linux中国象棋)