题解 P11030 『DABOI Round 1』Blessings Repeated

· · 题解

前言

出题人题解。

原题目名叫 Nice God's mOther marIa(NGOI)，但是为了比赛题目命名格式统一就改了，也算是个一语双关。

灵感来自对圣母名字的字符串进行一通操作，本来出的题太简单了，加强了一下就成了现在这个样子。

难度感觉也就绿蓝的样子。

题意

参见形式化题意。

分析

令 n = \vert S \vert , m = \vert T \vert。

测试点 1,2

性质 m \le 1，即字符串 T 只有一个字符。

问题就转化为了 k 个首尾相接的字符串 S 中出现了多少个 T 字符。

于是直接统计 S 中出现了多少次，答案乘 k 即可，时间复杂度 O(n)。

k=int(input())
s=input()
t=input()
print(s.count(t)*k%998244353)

测试点 3

性质 k=1，直接枚举两边字符即可，时间复杂度 O(n ^ 2)。

//the code is from chenjh
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int mod=998244353;
int n,m;
LL k;
char s[5005],t[11];
int main(){
    scanf("%lld %s %s",&k,s,t),n=strlen(s),m=strlen(t);
    int ans=0;
    for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)
        (ans+=s[i]==t[0]&&s[j]==t[1])>=mod&&(ans-=mod);
    printf("%d\n",ans);
    return 0;
}

测试点 4,5

和上一部分不同之处在于 k 的范围扩大到了 k \le 100，也就是说 k n \le 5 \times 10^5。

统计满足的二元组数量，只需要枚举一维，快速算另一维即可。

前缀和统计一下 T_0 的数量，遇到 T_1 相加一下即可，时间复杂度 O(k n)。

//the code is from chenjh
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int mod=998244353;
int n,m;
LL k;
char s[5005],t[11];
int main(){
    scanf("%lld %s %s",&k,s,t),n=strlen(s),m=strlen(t);
    int ans=0,w=0;
    while(k--)for(int i=0;i<n;i++) s[i]==t[1]&&(ans+=w)>=mod&&(ans-=mod),w+=s[i]==t[0];
    printf("%d\n",ans);
    return 0;
}

测试点 6,7

根据测试点 3 的方式直接枚举判断即可，时间复杂度 O(n ^ {m})，代码过于简单就不放了。

测试点 8,9,10

各种数据范围都相比前面的有所加强，所以不能暴力枚举了，考虑动态规划。

状态设计

设 f_{i,j} 表示字符串 s 前 i 个字符中 T 前 j 个字符组成的字符串出现的子序列方案数。

初始状态

f_{0,0}=1

状态转移

f_{i,j} = f_{i-1,j} + [s_{i-1} = T_{j-1}] f_{i-1,j-1}

答案即 f_{k n,m}。

时间复杂度 O(k n m)，空间复杂度可以滚动优化到 O(m)。

//the code is from chenjh
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int mod=998244353;
int n,m;
LL k;
char s[5005],t[11];
int f[11];
int main(){
    scanf("%lld %s %s",&k,s,t),n=strlen(s),m=strlen(t);
    *f=1;
    while(k--)for(int i=0;i<n;i++)for(int j=m;j>0;--j)s[i]==t[j-1]&&(f[j]+=f[j-1])>=mod&&(f[j]-=mod);
    printf("%d\n",f[m]);
    return 0;
}

测试点 11 \sim 20

对于每一个小写字母 $x$ 构造一个 $(m+1) \times (m+1)$ 的矩阵 $A_x$： $$ A_{x,i,j}= \begin{cases} 1 & i=j\\ [T_i = x] & j=i+1\\ 0 & \text{otherwise} \end{cases} $$ 接着设矩阵 $B=\prod\limits_{i=0}^{n-1}A_{S_i}$。 构造 $F$ 矩阵： $$ \begin{bmatrix} F_0 & F_1 & \dots & F_m \end{bmatrix} = \begin{bmatrix} 1 & 0 & \dots & 0 \end{bmatrix} $$ 最后将 $F \gets F \times B^k$ 即可，答案即为 $F_m$。 时间复杂度 $O(n m ^3)$，其中矩阵快速幂的时间复杂度为 $O(\log k m ^3)$。 ## 代码 ```cpp //the code is from chenjh #include<cstdio> #include<cstring> using namespace std; typedef long long LL; const int mod=998244353; template<typename T> struct Mat{//封装矩阵类。 int n,m; T **a; Mat(int _n=0,int _m=0):n(_n),m(_m){ a=new T*[n]; for(int i=0;i<n;i++) a[i]=new T[m],memset(a[i],0,sizeof(T)*m); } Mat(const Mat&B){ n=B.n,m=B.m; a=new T*[n]; for(int i=0;i<n;i++) a[i]=new T[m],memcpy(a[i],B.a[i],sizeof(T)*m); } ~Mat(){delete[] a;} Mat&operator = (const Mat&B)&{ delete[] a; n=B.n,m=B.m; a=new T*[n]; for(int i=0;i<n;i++) a[i]=new T[m],memcpy(a[i],B.a[i],sizeof(T)*m); return *this; } Mat operator * (const Mat&B)const{//矩阵乘法。 Mat ret(n,B.m); for(int i=0;i<n;++i)for(int j=0;j<B.m;++j)for(int k=0;k<m;++k)ret.a[i][j]=(ret.a[i][j]+(LL)a[i][k]*B.a[k][j]%mod)%mod; return ret; } Mat&operator *= (const Mat&B)&{return *this=*this*B;} }; LL k; int n,m; char s[5005],t[15]; int main(){ scanf("%lld %s %s",&k,s,t),n=strlen(s),m=strlen(t); Mat<int> F(1,m+1),A[26],B(m+1,m+1); for(int j=0;j<=m;j++) B.a[j][j]=1; **F.a=1; for(int i=0;i<26;i++){ A[i]=Mat<int>(m+1,m+1); for(int j=0;j<=m;j++) A[i].a[j][j]=1;//对于每一个字母构造单位矩阵。 } for(int i=0;i<m;i++) A[t[i]-'a'].a[i][i+1]=1;//将该转移位置的值为 1。 for(int i=0;i<n;i++) B*=A[s[i]-'a']; for(;k;k>>=1,B*=B)if(k&1)F*=B;//矩阵快速幂 printf("%d\n",F.a[0][m]); return 0; } ``` 据说还有一些其他的做法，但是我不会，欢迎大家提出自己的不同意见！