CF666C ，一道神奇的字符串计数题。
题目链接：CodeForces 666C。
题目
题意
有 \(m\) 组询问，询问有两种类型：
- \(t=1\)，给出字符串 \(s\)，要修改当前字符串为 \(s\)；
- \(t=2\)，给定整数 \(n\)，求有多少个长度为 \(n\) 字符串的字符串满足：\(s\) 是它的子序列。答案对 \(10^9+7\) 取模。
数据范围
| 变量 | 数据范围 |
| 数据组数 \(m\) | \(1\leq m\leq 10^5\) |
| 字符串长度和 \(\sum |s|\) | \(\sum |s|\leq 10^5\) |
| \(n\) | \(1\leq n\leq 10^5\) |
时空限制
| 题目编号 | 时间限制 | 空间限制 |
| CodeForces 666C | \(6\text{s}\) | \(256\text{MiB}\) |
题解
CF666C ，神奇的题目，有多种解法。
解法 A（暴力）
用 \(|S|\) 表示字符集的大小。
不妨设 \(f _ {i,j}\) 表示当前字符串长度为 \(i\)，与 \(s\) 的最长公共子序列的长度为 \(j\)。
那么我们有转移
\[f _ {i,j}=f _ {i-1,j-1}+(|S|-1)f _ {i-1,j}\]
这种做法是 \(\Theta(n\sum |s|)\) 的，显然会超时。
解法 B（优化）
考虑枚举最先匹配完 \(s\) 的位置为 \(i\)，即 \(s\) 是 相应字符串的子串 \([1,i]\) 的子序列。
对于这个位置 \(i\)，它后面可以乱选，所以对答案的贡献为 \(|S|^{n-i}\)。
对于这个位置 \(i\)，它前面有 \(|s|\) 个位置要与给定的字符串匹配，我们不妨设每一个匹配字符（最先匹配到的），都把从它到下一个匹配字符前分成一段，所以要选择 \(|s|-1\) 段（最后一个字符在 \(i\) 出单独一个点），分段的方案对答案的贡献为 \(\binom{i-1}{|s|-1}\)，对于每一段中，除了匹配字符以外的字符不能与下一个匹配字符相同，所以有 \(|S|-1\) 种选法，对答案的贡献为 \((|S|-1)^{i-|s|}\)。
所以最终的答案为
\[\texttt{ans}=\sum^n _ {i=|s|}(|S|-1)^{i-|s|}|S|^{n-i}\binom{i-1}{|s|-1}\]
这样的做法还是 \(\Theta(n\sum |s|)\) 的。
我们可以继续化简
\[
\begin{aligned}
\texttt{ans}&=\sum^n _ {i=|s|}(|S|-1)^{i-|s|}|S|^{n-i}\binom{i-1}{|s|-1}\\
&=|S|^n\sum^n _ {i=|s|}(|S|-1)^{i-|s|}|S|^{-i}\binom{i-1}{|s|-1}\\
&=26^n\sum^n _ {i=|s|}25^{i-|s|}26^{-i}\binom{i-1}{|s|-1}
\end{aligned}
\]
不难发现 \(\sum\) 里面的东西与 \(n\) 无关，且对于相同的 \(s\)，答案只与 \(n\) 的数值有关。
所以我们可以离线处理这道题目，对于 \(s\) 相同的询问，储存起来，后面按 \(n\) 排序，然后单调地处理 \(\sum\) 里面的东西，最后答案再乘上外面的 \(26^n\) 即可。
根据势能分析法，这种做法的时间复杂度为 \(\Theta(\sum |s|\sqrt{n})\)。
值得注意的是，这道题目需要预处理出许多数组（不然复杂度会多一个 \(\log _ 2n\)），具体可以看代码。
代码
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define MOD 1000000007
inline int read(void){
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return res;
}
const int MAXLEN=100000+5;
const int MAXN=100000+5;
const int MAXM=100000+5;
int fac[MAXN],finv[MAXN];
int pow25[MAXN],pow26[MAXN];
int invpow26[MAXN];
inline void Init(reg int n=1e5){
fac[0]=finv[0]=pow25[0]=pow26[0]=invpow26[0]=1;
finv[n]=716327852ll;
for(reg int i=1;i<=n;++i){
fac[i]=1ll*fac[i-1]*i%MOD;
pow25[i]=25ll*pow25[i-1]%MOD;
pow26[i]=26ll*pow26[i-1]%MOD;
invpow26[i]=576923081ll*invpow26[i-1]%MOD;
}
for(reg int i=n-1;i>=1;--i)
finv[i]=1ll*finv[i+1]*(i+1ll)%MOD;
return;
}
inline int C(reg int n,reg int m){
return 1ll*fac[n]*finv[m]%MOD*finv[n-m]%MOD;
}
struct Node{
int id,val;
inline Node(reg int id=0,reg int val=0):id(id),val(val){
return;
}
inline bool operator<(const Node& a)const{
return val<a.val;
}
};
char str[MAXLEN];
Node S[MAXM];
int top;
int ans[MAXM];
inline void Solve(void){
sort(S+1,S+top+1);
reg int l=strlen(str);
reg int sum=0,ptr=l;
for(reg int i=1;i<=top;++i){
reg int r=S[i].val;
for(;ptr<=r;++ptr)
sum=(sum+1ll*pow25[ptr-l]*invpow26[ptr]%MOD*C(ptr-1,l-1)%MOD)%MOD;
ans[S[i].id]=1ll*sum*pow26[r]%MOD;
}
for(reg int i=1;i<=top;++i)
printf("%d\n",ans[i]);
top=0;
return;
}
int main(void){
Init();
reg int m=read();
scanf("%s",str);
while(m--){
reg int t=read();
switch(t){
case 1:{
Solve();
scanf("%s",str);
break;
}
case 2:{
reg int n=read();
++top;
S[top]=Node(top,n);
break;
}
default:break;
}
}
Solve();
return 0;
}
近期评论