问题套了一个斐波那契数，归根结底就是要求对于所有后缀s[i...n-1]，所有前缀在其中出现的总次数。我一开始做的时候想了好久，后来看了别人的解法才恍然大悟。对于一个后缀来说 s[i...n-1]来说，所有与它匹配的前缀必然是和 s[i+1...n-1] s[i+2...n-1] ....s[n-1..n-1]里的前缀匹配的，因而如果我们定义一个num[i]表示的是后缀s[i...n-1]与前缀的总长公共前缀，那么num[i]+num[i+1]+..num[n-1]就是前缀在后缀i里出现的次数总和，所以问题转化为求s[i...n-1]跟前缀的最长公共前缀，也可以理解成是 s[0...n-1]和s[i...n-1]求最长公共前缀。
求后缀的最长公共前缀，一个做法是后缀数组，然后建lcp,然后通过rmq询问，理论的复杂度nlogn,我自己套的模板用的是快排，所以后缀数组本身的复杂度就已经是nlog^2n，然后我就愉快的TLE了。
失败之后就只能转而用hash＋二分，毕竟二分还是慢，所以我卡着时限过了这题，心有余悸。
#pragma warning(disable:4996)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std; #define maxn 110000
#define ll long long
#define mod 1000000007
#define step 31 /*int rk[maxn], sa[maxn], lcp[maxn];
int tmp[maxn];
int d[maxn + 50][25];*/ int n; /*bool cmp_sa(int i, int j)
{
if (rk[i] != rk[j]) return rk[i] < rk[j];
else{
int ri = i + k <= n ? rk[i + k] : -1;
int rj = j + k <= n ? rk[j + k] : -1;
return ri < rj;
}
} void construct_sa(char *s, int *sa)
{
n = strlen(s);
for (int i = 0; i <= n; i++){
sa[i] = i;
rk[i] = i < n ? s[i] : -1;
}
for (k = 1; k <= n; k <<= 1){
sort(sa, sa + n + 1, cmp_sa);
tmp[sa[0]] = 0;
for (int i = 1; i <= n; i++){
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp_sa(sa[i - 1], sa[i]) ? 1 : 0);
}
for (int i = 0; i <= n; i++){
rk[i] = tmp[i];
}
}
} void construct_lcp(char *s, int *sa, int *lcp)
{
n = strlen(s);
for (int i = 0; i <= n; i++) rk[sa[i]] = i;
int h = 0;
lcp[0] = 0;
for (int i = 0; i < n; i++){
int j = sa[rk[i] - 1];
for (h ? h-- : 0; i + h < n&&j + h < n&&s[i + h] == s[j + h]; h++);
lcp[rk[i] - 1] = h;
}
} void construct_rmq(int *lcp, int sizen)
{
for (int i = 0; i <= sizen; i++) d[i][0] = lcp[i];
for (int j = 1; (1 << j) <= sizen; j++){
for (int i = 0; (i + (1 << j) - 1) <= sizen; i++){
d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
}
}
} int rmq_query(int l, int r)
{
if (l > r) swap(l, r); r -= 1;
int k = 0; int len = r - l + 1;
while ((1 << (k + 1)) < len) k++;
return min(d[l][k], d[r - (1 << k) + 1][k]);
} */ char s[maxn];
ll num[maxn]; struct Matrix
{
ll a[2][2];
Matrix(){ memset(a, 0, sizeof(a)); }
}m; Matrix operator * (const Matrix &a,const Matrix &b){
Matrix ret;
for (int i = 0; i < 2; i++){
for (int j = 0; j < 2; j++){
for (int k = 0; k < 2; k++){
ret.a[i][j] += (a.a[i][k] * b.a[k][j]) % mod;
ret.a[i][j] %= mod;
}
}
}
return ret;
}
Matrix operator ^ (Matrix a,ll n){
Matrix ret;
for (int i = 0; i < 2; i++) ret.a[i][i] = 1;
while (n){
if (n & 1) ret = ret*a;
n >>= 1;
a = a*a;
}
return ret;
} ll cal(ll n)
{
m.a[0][0] = 0; m.a[0][1] = 1;
m.a[1][0] = 1; m.a[1][1] = 1;
m = m^n;
return m.a[0][1];
} ll seed[maxn];
ll h[maxn]; ll get(int l, int r){
return ((h[r] - h[l - 1] * seed[r - l + 1]%mod) + mod) % mod;
} int getlcp(int x)
{
if (get(1, 1) != get(x, x)) return 0;
int l = 1,r = n - x + 1;
while (l <= r){
int m = (l + r) >> 1;
if (get(1, 1 + m - 1) == get(x, x + m - 1)) l = m+1;
else r = m-1;
}
return r;
} int main()
{
seed[0] = 1;
for (int i = 1; i < maxn; i++){
seed[i] = seed[i - 1] * step%mod;
}
while (~scanf("%s", s + 1))
{
n = strlen(s + 1); h[0] = 0;
for (int i = 1; i <= n; i++){
h[i] = (h[i - 1] * step + s[i]) % mod;
}
num[1] = n;
for (int i = 2; i <= n; i++){
num[i] = getlcp(i);
}
ll ans = 0;
num[n + 1] = 0;
for (int i = n; i >= 1; i--){
num[i] += num[i + 1];
ans += cal(num[i]);
ans %= mod;
}
printf("%lld\n", ans);
}
return 0;
}