题目链接：传送门

Description

给你一个串,定义了一个权值和,每个权值是两个回文串拼起来的左右坐标乘积

Solution

设R[i]为所有以 i 为右端点的回文字串的左端点之和，同理，L[i]表示所有以 i 为左端点的回文子串的右端点之和。显然，答案为

TeX parse error: Undefined control sequence \[

对于L和R，我们可以考虑对每个以i为中心的回文串算贡献，用类似差分+前缀和的思想可以O(1)修改，最后O(N)遍历一遍即能求出

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int Maxn = 2e6 + 10, Mod = 1000000007;

char S[Maxn], A[Maxn];
int P[Maxn];
int Sum1[Maxn], Sum2[Maxn];
int L[Maxn], R[Maxn];

int N;

inline void Init ()
{
    memset(P, 0, sizeof P);
    memset(A, 0, sizeof A);
    memset(L, 0, sizeof L);
    memset(R, 0, sizeof R);
    memset(Sum1, 0, sizeof Sum1);
    memset(Sum2, 0, sizeof Sum2);
}

inline void Manacher ()
{
    N = strlen(S + 1);
    for (int i = 1; i <= N; ++i)
        A[i * 2] = S[i], A[i * 2 - 1] = '#';
    A[0] = '%', A[N * 2 + 1] = '#';
    N = N * 2 + 1;
    for (int i = 0; i <= N; ++i) S[i] = A[i];

    int id = 0, Max = 0;
    for (int i = 1; i <= N; ++i)
    {
        if (i < Max)
            P[i] = min(P[2 * id - i], Max - i);
        else P[i] = 1;
        while (S[i + P[i]] == S[i - P[i]]) P[i] ++;
        if (Max < i + P[i] - 1)
        {
            Max = i + P[i] - 1;
            id = i;
        }
    }
}

inline void Solve ()
{
    Manacher();
    for (int i = 1; i <= N; ++i)
    {
        Sum1[i - P[i] + 1] += i, Sum1[i + 1] -= i;
        Sum2[i - P[i] + 1] ++, Sum2[i + 1] --;
    }
    for (int i = 1; i <= N; ++i)
    {
        Sum1[i] += Sum1[i - 1], Sum2[i] += Sum2[i - 1];
        if (!(i % 2)) L[i / 2] = (Sum1[i] - i / 2 * Sum2[i]) % Mod;
    }

    memset(Sum1, 0, sizeof Sum1);
    memset(Sum2, 0, sizeof Sum2);

    for (int i = 1; i <= N; ++i)
    {
        Sum1[i] += i, Sum1[i + P[i]] -= i;
        Sum2[i] ++, Sum2[i + P[i]] --;
    }
    for (int i = 1; i <= N; ++i)
    {
        Sum1[i] += Sum1[i - 1], Sum2[i] += Sum2[i - 1];
        if (!(i % 2)) R[i / 2] = (Sum1[i] - i / 2 * Sum2[i]) % Mod;
    }

    int Ans = 0ll;
    N /= 2;
    for (int i = 1; i < N; ++i)
        (Ans += L[i + 1] * R[i] % Mod) %= Mod;
    cout<<Ans<<endl;

}

main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    while (~scanf("%s", S + 1))
    {
        Init();
        Solve();
        memset(S, 0, sizeof S);
    }
    return 0;
}