题目链接

题面：

题意：
给定一个字符串
求 ∑ i = 1 n p i ∗ 111 2 i − 1 \sum_{i=1}^np_i*1112^{i-1} ∑i=1n​pi​∗1112i−1
其中， p i p_i pi​ 是字符串 S 的前缀 S i S_i Si​ 的所有后缀的最小后缀的位置。

题解：
考虑Lyndon 分解过程。
Lyndon 分解：读入一个字符串S，把这个字符串分解成若干部分 S = S 1 S 2 . . . S k S=S_1S_2...S_k S=S1​S2​...Sk​
其中每一个 S i S_i Si​都是Lyndon串，且有 S i > = S i + 1 S_i>=S_{i+1} Si​>=Si+1​

一个字符串S是一个Lyndon串，当且仅当S是其所有后缀中最小的字符串。
我们设当前读入的字符是 s [ k ] , j = k − ∣ t ∣ s[k],j=k-|t| s[k],j=k−∣t∣，t 是正在循环的 Lyndon串。

如果 s [ k ] > s [ j ] s[k]>s[j] s[k]>s[j] 新的Lyndon串(循环)被固定下来，那么 S k S_k Sk​的 P k = i P_k=i Pk​=i
如果 s [ k ] = s [ j ] s[k]=s[j] s[k]=s[j] 周期 k − j k-j k−j继续保持， P k P_k Pk​等于其上一个循环节对应位置 最小后缀的位置往后移动一个循环节， j j j 是 k k k 上一个循环节所对应位置，那么 P j P_j Pj​往后移动一个循环节，即 P j + k − j P_j+k-j Pj​+k−j。
如果 s [ k ] = = s [ j ] s[k]==s[j] s[k]==s[j]那么循环中的Lyndon串被固定下来。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=1000100;
const int maxm=100100;
const int up=100000;

ll p[maxn];
int pos[maxn];
char str[maxn];


int main(void)
{
    p[0]=1;
    for(int i=1;i<maxn;i++)
        p[i]=p[i-1]*1112%mod;
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%s",str+1);
        int n=strlen(str+1);
        for(int i=1;i<=n;)
        {
            int j=i,k=i+1;
            //str[i]这个字符组成的字符串是找的最初始的lyndon串
            pos[i]=i;
            while(k<=n&&str[j]<=str[k])
            {
                if(str[j]<str[k]) pos[k]=i,j=i;
                else pos[k]=pos[j]+k-j,j++;
                k++;
            }
            while(i<=j) i+=k-j;
        }
        ll ans=0;
        for(int i=1;i<=n;i++)
            ans=(ans+p[i-1]*pos[i])%mod;
        printf("%lld\n",ans);
    }
    return 0;
}