集团网站设计欣赏,php网站建设教程,免费开通网站,建设厅网站给领导留言如何查看正题
题目链接:https://www.luogu.com.cn/problem/P5404 题目大意
给出一个字符串SSS#xff0c;然后求有多少个长度为mmm的串TTT满足。无限多个串TTT拼接起来后能找出一个长度和SSS相等的子串字典序比SSS小。 1≤∣S∣,m≤20001\leq |S|,m\leq 20001≤∣S∣,m≤2000 解题思…正题
题目链接:https://www.luogu.com.cn/problem/P5404 题目大意
给出一个字符串SSS然后求有多少个长度为mmm的串TTT满足。无限多个串TTT拼接起来后能找出一个长度和SSS相等的子串字典序比SSS小。
1≤∣S∣,m≤20001\leq |S|,m\leq 20001≤∣S∣,m≤2000 解题思路
首先有一个小于的很难找所以我们找有多少一直大于等于的减去就好了。
然后其实如果有一个大于位置大于SSS串匹配就可以直接不管所以其实我们主要考虑前面都相等的情况根据题解考虑用KMPKMPKMP。
设我们现在匹配到[1,k][1,k][1,k]然后有[1,nxtk][k−nxtk1,k][1,nxt_k][k-nxt_k1,k][1,nxtk][k−nxtk1,k]然后加了一个字符如果有跳的边而且是转移边里面字符最大的因为我们显然需要匹配出一个最大的前缀不然不能保证有小于的时候能直接找到。
而且如果我们现在在KMPKMPKMP上走了T∞T^{\infty}T∞之后节点是iii那么T∞TT^{\infty}TT∞T也是会匹配回到节点iii的所以相当于我们要找一个节点ppp使得它匹配了TTT之后仍然是回到节点ppp。
暴力枚举节点来dpdpdp肯定是会TTT考虑优化一下。
不难发现如果一个点走mmm步之后没有回到过000号节点的话方案只有一种因为每个点连接000以外的出边最多只有一条。
所以设fi,jf_{i,j}fi,j表示从000出发走jjj步到达iii的方案数。
然后对于起点枚举多少步后走到000再用fff统计答案就好了。
时间复杂度O(nm)O(nm)O(nm) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2100,P998244353;
ll n,m,ans,nxt[N],ch[N][26],f[N][N],mx[N];
char s[N];
signed main()
{scanf(%lld%s,m,s1);nstrlen(s1);ans1;for(ll i1;im;i)ansans*26ll%P;for(ll i2,j0;in;i){while(js[i]!s[j1])jnxt[j];j(s[i]s[j1]);nxt[i]j;}for(ll i0;in;i)for(ll c0;c26;c){if(s[i1]ca)ch[i][c]i1;else ch[i][c]ch[nxt[i]][c];if(ch[i][c])mx[i]c; }f[0][0]1;for(ll i0;im;i)for(ll j0;jn;j)for(ll cmx[j];c26;c)(f[ch[j][c]][i1]f[j][i])%P;for(ll i0;in;i){ll xi;for(ll j1;jm;j){(ans-(25-mx[x])*f[i][m-j]%P)%P;xch[x][mx[x]];if(!x)break;}if(ixi)(ansP-1)%P;}printf(%lld\n,(ansP)%P);return 0;
}
