问题套了一个斐波那契数，归根结底就是要求对于所有后缀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#include #include #include #include #include #include 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;}