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; }
近期评论