「题解」「CF666C」Codeword

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;
}

相关题目