学步园

http://www.lydsy.com/JudgeOnline/problem.php?id=3670

。。。。。。。多组数据ans=1，找了一个小时

这道题，首先随便写了暴力，亲测50分

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive    Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int read()
{int r=0,k=1;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';return k*r;}
/////////////////////////////////////////////////
int n;
char s[1000010];
int next[10000010];
/////////////////////////////////////////////////
void get_next()
{
	int i=0,j=-1;
	next[0]=-1;
	while(i<n)
	    if(j==-1||s[i]==s[j]) next[++i]=++j;
	    else j=next[j];
}
/////////////////////////////////////////////////
void input()
{
    scanf("%s",s);
    n=strlen(s);
}
void solve()
{
	LL ans=1;
    get_next();
    //rep(i,1,n) printf("%d ",next[i]);
    rep(i,1,n)
    {
    	int cnt=0;
    	for(int j=next[i];j>0;j=next[j])
    		if(j<=i/2) cnt++;
    	ans*=cnt+1;
    	ans%=1000000007L;
    }
    printf("%lld\n",ans);
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("std.out","w",stdout);
    #endif
    for(int T=read();T--;)
    input(),solve();
    return 0;
}

然后开始想优化

首先树状数组维护dfs序是很容易想到的，也很好写，O(nlogn)应该有点悬，略去

在这个关键的地方我找了下线性的题解

中间的while均摊是O(1)的，因此才保证了KMP的复杂度

再维护一个k就行了，还需脑补一下、、、

看来KMP需要换模板了

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive    Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int read()
{int r=0,k=1;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';return k*r;}
/////////////////////////////////////////////////
int n;
char s[1000010];
int next[1000010];
int num[1000010];
LL ans=1;
/////////////////////////////////////////////////
void get_next()
{
	int i,k=-1,j=-1;
	next[0]=-1;
	for(i=0;i<n;)
	{
	    while(j!=-1&&s[i]!=s[j]) j=next[j];
	    while(k!=-1&&s[i]!=s[k]) k=next[k];
	    i++;j++;k++;
	    next[i]=j;
	    num[i]=num[j]+1;
	    
	    while(k>(i>>1)) k=next[k];
	    ans*=num[k]+1;
    	ans%=1000000007L;
	}
}
/////////////////////////////////////////////////
void input()
{
	ans=1;
    scanf("%s",s);
    n=strlen(s);
}
void solve()
{
    get_next();
    printf("%lld\n",ans);
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("std.out","w",stdout);
    #endif
    for(int T=read();T--;)
    input(),solve();
    return 0;
}

Loriex:这题随便用nlogn的DP+二分斜率优化就可以水过去

无限仰慕随便水harbingers。。。。

Update Jan.12

今天换了模板发现完全不能理解当时写的啥，于是。。。

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive    Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int read()
{int r=0,k=1;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';return k*r;}
/////////////////////////////////////////////////
int n;
char s[1000010];
int next[1000010];
int num[1000010];
LL ans=1;
/////////////////////////////////////////////////
void get_next()
{
	int j=0,k=0;
	num[1]=1;
	rep(i,2,n)
	{
		while(j&&s[i]!=s[j+1]) j=next[j];
		while(k&&s[i]!=s[k+1]) k=next[k];
		next[i]=j+=s[i]==s[j+1]; k+=s[i]==s[k+1];
		num[i]=num[j]+1;
		while(k>(i>>1)) k=next[k];
	    ans*=num[k]+1;
    	ans%=1000000007L;
	}
}
/////////////////////////////////////////////////
void input()
{
	ans=1;
    scanf("%s",s+1);
    n=strlen(s+1);
}
void solve()
{
    get_next();
    printf("%lld\n",ans);
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("std.out","w",stdout);
    #endif
    for(int T=read();T--;)
    input(),solve();
    return 0;
}