首页 > 其他分享 >P5404 [CTS2019] 重复 题解

P5404 [CTS2019] 重复 题解

时间:2023-10-31 15:44:06浏览次数:40  
标签:字符 前缀 后缀 题解 ll P5404 CTS2019 include 节点

题目链接

观察题目,我们发现直接计算是困难的,先构造单个合法的 \(T\) 分析其性质。

为了构造出 \(T\),先考虑构造时 \(T\) 时什么时候会出现不合法的情况,此时 \(T\) 会有一段和 \(S\) 相同的前缀,且这段前缀后面跟着的字符比 \(S\) 所跟的小。

为了避免这种情况出现,我们需要在每次添加字符时进行检查,具体而言,我们需要保证当前字符串的任意一个为 \(S\) 前缀的后缀在 \(S\) 中的下一个字符小于等于当前的字符。

这个约束条件显然与 KMP 有点关联,我们边加字符边维护当前字符串的一个最长的为 \(S\) 前缀的后缀,相当于建出 \(S\) 的 KMP 自动机,维护当前所在节点,每次直接跳向上的转移边查找约束后即可合法构造。

接下来考虑 \(T\) 开始循环后在自动机上会怎样转移,考察在输入无穷次 \(T\) 后走到的一个节点,由于 KMP 自动机的节点主要代表当前字符串与 \(S\) 的一个前缀相同的最大后缀的长度,且输入的长度无穷大,因此如果我们再输入一次 \(T\),此串与 \(S\) 的一个前缀相同的最大后缀的长度不改变,即还会回到原本的节点,故此过程构成了一个环,直接硬 dp \(m\) 次找环的个数可以做到 \(O(n^2m)\)。

如何优化呢?考察我们 dp 找环时每次转移往待定 \(T\) 的末尾添加字符,先找到我能放置的最小的字符,即待定 \(T\) 与 \(S\) 的一个前缀相同的所有后缀中下一个字符最大的那个,如果更小就不合法,要么添加此字符要么再添加更大的。

如果添加此字符,则继续往下转移,否则因为 \(S\) 中没有对应的前缀,我们会回到根节点。

故此过程对于以每个节点为起点的环,不过根节点的环最多只有一个(沿唯一的路径一直走,因此我们可以暴力判断存不存在此环,并枚举走到根节点的最小时间,在此时间之前我们沿着既定路线走,之后跳到根节点再走回来,走回来的方案数可以 dp 预处理,设 \(f_{i,j}\) 表示到达第 \(i\) 个节点走了 \(j\) 步的方案数,转移是容易的。

两个部分综合起来时间复杂度 \(O(nm)\)。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 3005
#define mod 998244353
#define ll long long
using namespace std;
char s[N];
ll nex[N],maxpos[N],ch[N][27],f[N][N];
int main(){
	ll m;cin>>m;cin>>(s+1);ll n=strlen(s+1);
	ll sum=1;
	for(ll i=1;i<=m;i++)sum=(sum*26)%mod;
	for(ll i=2,j=0;i<=n;i++){
		while(j && s[i]!=s[j+1])j=nex[j];
		if(s[i]==s[j+1])j++;
		nex[i]=j;
	}
	for(ll i=0;i<=n;i++){
		for(ll j=1;j<=26;j++){
			if(s[i+1]-'a'+1==j)ch[i][j]=i+1;
			else ch[i][j]=ch[nex[i]][j];
			if(ch[i][j])maxpos[i]=j;
		}
	}
	f[0][0]=1;
	for(ll j=0;j<=m;j++){
		for(ll i=0;i<=n;i++){
			for(ll k=maxpos[i];k<=26;k++)f[ch[i][k]][j+1]=(f[ch[i][k]][j+1]+f[i][j])%mod;
		}
	}
	ll ans=0;
	for(ll i=0;i<=n;i++){
		ll now=i;
		for(ll j=1;j<=m;j++){
			ans=(ans*1ll+(26-maxpos[now])*1ll*f[i][m-j])%mod;
			now=ch[now][maxpos[now]];
			if(!now)break;
		}
		if(now==i)ans=(ans+1)%mod;
	}
	cout<<(((sum-ans)%mod)+mod)%mod;
}

标签:字符,前缀,后缀,题解,ll,P5404,CTS2019,include,节点
From: https://www.cnblogs.com/eastcloud/p/17800409.html

相关文章

  • CSPRO 历届题目与题解
    官方题目链接:http://118.190.20.162/\(\Huge目录\)201609201612201709202104202109202112202203202206202209202303202305202309\(\Huge\text{CSP201609}\)火车购票问题描述请实现一个铁路购票系统的简单座位分配算法,来处理一节车厢的座位分配。假设一节车厢......
  • AT_abc326_d ABC Puzzle 题解
    AT_abc326_dABCPuzzle题解看题事实上,即使在\(N=5\)的情况下,也只有\(66240\)个网格满足「每行/每列恰好包含一个A、B和C」。——官方题解其实看到这道题,就感觉是搜索,这很显然。但是我们会发现,最最最native的搜索,是\(4^{5\times5}=2^{50}\)的。感觉不大可过,但是......
  • AT_abc326_e Revenge of "The Salary of AtCoder Inc." 题解
    AT_abc326_eRevengeof"TheSalaryofAtCoderInc."题解一道简单的概率论+动态规划题目(然而我赛时没看这道题题意有一个长度为\(n\)的序列\(A\)、一个\(n\)面骰子,掷若干次骰子,如果这一次掷骰子的点数小于等于上一次的点数,则结束。定义这若干次掷骰子的总的结果为,每次......
  • AT_abc326_f Robot Rotation 题解
    AT_abc326_fRobotRotation题解经典问题,以前遇到过一个类似的问题:[ABC082D]FTRobot。建议对比着看一看这两道题,是两种不同的思路。(那一道题不用输出方案,因此可以用bitset优化;而此题需要输出方案,因此需要双向搜索。思路注意到每次只能「左转」和「左转」。所以,偶数次走......
  • AT_abc325_f Sensor Optimization Dilemma 题解
    AT_abc325_fSensorOptimizationDilemma题解Date20231025:修复手滑公式\(\min\)、\(\max\)写反了。动态规划。类似背包问题。朴素算法记\((x,y)\)表示使用\(x\)个(1)传感器、\(y\)个(2)号传感器。设\(f(t,i,j)\)表示覆盖前\(t\)个区间,使用\((i,j)\)传感......
  • AT_abc325_g offence 题解
    AT_abc325_goffence题解一道不难但是需要想一想的区间DP。有一个比较复杂的例子:ooofofxxx,简单的分析可知,一个of后面删除多少,与其前、后都有关,于是考虑区间DP。想到这里,其实问题已经解决一半了。状态设计设\(f(l,r)\)为闭区间\([l,r]\)经过操作之后的最小长度。注......
  • [CSP-S2020] 儒略日 题解
    [CSP-S2020]儒略日今儿终于做掉困扰多年的题目了,其实想好细节也不难。容易发现儒略历和格里高利历的润年判断方式不一样,并且中间有消失的十天,计算起来相当不方便。所以我们可以首先计算出\(-4713.1.1\)~\(1582.10.4\)会经过多少天,可以通过一天一天暴力跳的方法计算出需要\(......
  • P4309 [TJOI2013] 最长上升子序列题解
    P4309[TJOI2013]最长上升子序列题解正文单调队列?单调锤子队列!!本题的操作可以省略成:单点修改区间查询好极了,此时我们有两种选择:线段树和树状数组,(平衡树,真不会,下一位因为不需要其他操作,所以我们还是选择更小巧更可爱的树状数组吧。关于vectorvector的insert操作支......
  • 题解 ABC326G【Unlock Achievement】
    题解ABC326G【UnlockAchievement】problem有\(n\)项属性,第\(j\)个属性的等级\(l_j\)初始为\(1\),每提升一级花费\(c_j\)的钱。又有\(m\)项成就,第\(i\)项成就要求对于所有\(1\leqj\leqn\),都要\(l_j\geqL_{i,j}\),如果满足所有要求,获得\(a_i\)的钱。求你最多......
  • ADASTRNG - Ada and Substring 题解
    ADASTRNG-AdaandSubstring题解题目描述给定一个小写字符串。输出\(26\)个数,代表以\(\texttt{a}\sim\texttt{z}\)开头的本质不同的子串个数。题目分析高度数组模板题。可以想到将以每个字符开头的本质不同的子串数目转化为:以每个字符开头的所有字串数目减去以每......