【Bzoj3670】【Luogu2375】动物园

Source and Judge

Bzoj3670
Luogu2375

Problem

【Description】
对于字符串S的前i个字符构成的子串,既是它的后缀同时又是它的前缀,并且该后缀与该前缀不重叠,将这种字符串的数量记作num[i]。输出所有(num[i]+1)的乘积,对1,000,000,007取模的结果即可。
【Input】
第1行仅包含一个正整数n ,表示测试数据的组数。随后n行,每行描述一组测试数据。
每组测试数据仅含有一个字符串S,S的定义详见题目描述。
【Output】
包含 n 行,每行描述一组测试数据的答案,答案的顺序应与输入数据的顺序保持一致。对于每组测试数据,仅需要输出一个整数,表示这组测试数据的答案对 1,000,000,007 取模的结果。
【Limited conditions】
S中仅含小写字母。
1 N ≤ 5, L ≤ 50
2 N ≤ 5, L ≤ 200
3 N ≤ 5, L ≤ 200
4 N ≤ 5, L ≤ 10,000
5 N ≤ 5, L ≤ 10,000
6 N ≤ 5, L ≤ 100,000
7 N ≤ 5, L ≤ 200,000
8 N ≤ 5, L ≤ 500,000
9 N ≤ 5, L ≤ 1,000,000
10 N ≤ 5, L ≤ 1,000,000
【Sample input】
3
aaaaa
ab
abcababc
【Sample output】
36
1
32
【Sample explanation】
S为aaaaa,则num[4] = 2。
这是因为S的前4个字符为aaaa,其中a和aa都满足性质‘既是后缀又是前缀’,同时保证这个后缀与这个前缀不重叠。
而aaa虽然满足性质‘既是后缀又是前缀’,但遗憾的是这个后缀与这个前缀重叠了,所以不能计算在内。
同理,num[1] = 0,num[2] =1, num[3] = 1,num[5] = 2

Record

1h

Analysis

请先思考

一开始看错题以为是对于当前前缀的长度,以为就kmp特判一下……然后手玩数据才发现错

  1. 用kmp搞出nxt数组(注意不重叠的条件暂时不理,否则会影响后面)
  2. 用一个x表示上一次的合法值,然后转移为当前i的nxt值(不一定最大)
    (这一步不能偷懒直接用nxt[i],否则前功尽弃,50分)
  3. 跳nxt直到满足条件
  4. 记录一个【无视条件的个数】的sum,然后直接继承

有没有感觉这个sum和num的关系,很像是莫比乌斯反演中F和f的关系
都是从题目要求的,但是很困难的,先计算类似但范围更大而且容易计算的的,然后推导出题目要求的,这种思想非常值得学习。

Code

请先思考
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
void chmax(int &x,int y) {if(x<y) x=y;}
void chmin(int &x,int y) {if(x>y) x=y;}
//*******************全局常量*******************
const int MAXN=1100000;
const int MOD=1e9+7;
//*******************全局定义*******************
char s[MAXN];
int nxt[MAXN];
ll sum[MAXN];
//*******************实现*******************
//*******************主函数*******************
int main()
{
int T;scanf("%d",&T);
while(T--)
{
scanf("%s",s+1);
int ln=strlen(s+1);
ll ans=1;nxt[1]=0;sum[1]=1;//debug
int x=0;
for(int i=2;i<=ln;i++)
{
int j=nxt[i-1];
while(j>0 and s[j+1]!=s[i]) j=nxt[j];
nxt[i]=j+(s[j+1]==s[i]);
sum[i]=sum[nxt[i]]+1;
while(x>0 and s[x+1]!=s[i]) x=nxt[x];
if(s[x+1]==s[i]) x++;
while(x>0 and !(x*2<=i)) x=nxt[x];
ans=(ans*(sum[x]+1))%MOD;
}
printf("%lld\n",ans);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-04/动物园.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%