[国家集训队] 拉拉队排练

标签: #manacher #dp
原题目: luogu-P1659
简要描述: manacher算法➕贡献思维

题目分析

问题转化

题目要求找到所有"和谐小群体"，即：

  • 连续的一段女生，有奇数个
  • 她们手中的牌子字母从左到右和从右到左读起来一样

这实际上就是寻找字符串中的所有奇数长度回文子串。

核心思路

  1. 统计所有奇数长度回文子串的数量
  2. 按长度降序排序，取前K个长度的乘积
  3. 处理模运算和不足K个的情况

算法设计

第一步：Manacher算法找所有回文

使用Manacher算法可以在O(n)O(n)时间内找到以每个位置为中心的最长回文半径。

对于每个中心位置，如果我们得到半径为r，那么以该为中心的奇数回文子串有：

  • 长度为1, 3, 5, …, 2r-1
  • 共r个回文子串

第二步：统计各长度回文数量

使用cnt[i]表示长度为i的回文子串数量。

朴素做法的问题： 如果直接遍历每个中心，然后枚举所有可能的回文长度，时间复杂度为O(n2)O(n^2)。

优化思路 - 贡献法： 观察到回文的嵌套性质：

  • 长度为i的回文内部包含长度为i-2的回文
  • 长度为i-2的回文内部包含长度为i-4的回文
  • …

因此，我们可以：

  1. 先统计每个中心的最长回文长度
  2. 然后从大到小累加贡献：
    cpp
    copy 
            
    1
    2
    3
    4
    
        for(int i = n; i-2 >= 0; i--) {
    cnt[i-2] += cnt[i];
}

这样每个长度为i的回文会向所有更小的奇数长度贡献1个回文。

第三步：计算答案

从大到小遍历长度，累乘前K个：

cpp
copy 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

        ll ans = 1;
for(int i = n; i >= 1; i--) {
    if(i % 2 == 1) {  // 只考虑奇数长度
        if(k >= cnt[i]) {
            ans *= quick_pow(i, cnt[i]);
            ans %= mod;
            k -= cnt[i];
        } else {
            ans *= quick_pow(i, k);
            ans %= mod;
            k = 0;
            break;
        }
    }
}

复杂度分析

  • Manacher算法：O(n)O(n)
  • 贡献统计：O(n)O(n)
  • 答案计算：O(n)O(n)
  • 总时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)

关键点

  1. Manacher算法的正确应用：理解变换后的字符串与原字符串的对应关系
  2. 贡献法的巧妙运用：避免O(n2)O(n^2)的暴力统计
  3. 模运算和快速幂：处理大数乘法
  4. 边界情况处理：不足K个时输出-1
cpp
copy 
        
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

        /**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * date: 2025-12-14 09:04:01
 * oj: luogu-1659
 * title: [国家集训队] 拉拉队排练
 * description: manacher
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
const int maxn = 2e6+5;
ll mod = 19930726;
ll n,m,k;
char s[maxn];
ll cnt[maxn]; // cnt[i] 表示长度为的回文串的数量



// Manacher 模板（不使用 std::string）
struct Manacher {
    // 变换后长度上限：2*MAXN + 少量哨兵
    static const int SZ = maxn * 2 + 5;
    char t[SZ];    // 变换后的字符串：^ # a # b # ... # $
    int p[SZ];     // 半径数组（在 t 上的扩展长度）
    int m = 0;     // t 的实际长度（含终止符）

    // 构造变换串并计算 p[]
    // 输入：C 风格字符串 s（以 '\0' 结尾）
    void build(const char *s) {
        int n = (int)strlen(s);
        int k = 0;
        t[k++] = '&';   // 左哨兵，防止越界
        t[k++] = '#';
        for (int i = 0; i < n; ++i) {
            t[k++] = s[i];
            t[k++] = '#';
        }
        t[k++] = '^';   // 右哨兵
        t[k] = '\0';
        m = k;

        // 初始化半径数组
        memset(p,0,sizeof(p));

        // Manacher 主循环
        int center = 0, right = 0;
        for (int i = 1; i < m - 1; ++i) {
            int mirror = 2 * center - i;
            if (i < right) p[i] = min(right - i, p[mirror]);
            else p[i] = 1; // 长度至少是1

            // 暴力扩展：安全因为有哨兵
            while (t[i + p[i]] == t[i - p[i]]) ++p[i];

            int len = p[i] - 1;
            cnt[len]++;

            // 更新中心与右边界
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
        }
    }

    // 获取最长回文子串，返回长度；通过引用参数 l,r 返回原串上的左闭右闭索引（0-based）
    int longest(int &l, int &r) const {
        int best_len = 0, best_center = 0;
        for (int i = 1; i < m - 1; ++i) {
            if (p[i]-1 > best_len) {
                best_len = p[i]-1;
                best_center = i;
            }
        }
        if (best_len == 0) { l = 0; r = -1; return 0; }
        // 将 t 中的位置映射回原串的索引
        l = (best_center - best_len) / 2;
        r = l + best_len - 1;
        return best_len;
    }
};

Manacher man;

// int main() {
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);
//
//     static char s[MAXN + 5];
//     if (scanf("%s", s) != 1) return 0;   // 读取一个单词（竞赛常用）
//     // 若需读取整行（含空格），使用 fgets 或 fgets + 去除末尾换行
//
//     Manacher man;
//     man.build(s);
//
//     int L, R;
//     int len = man.longest(L, R);
//     printf("%d\n", len);
//     if (len > 0) {
//         // 输出子串：注意 printf 的 %.*s 用法
//         printf("%.*s\n", len, s + L);
//     }
//     return 0;
// }
void init(){
    std::cin >> n >> k;
    cin >> s;
    man.build(s);
}

ll quick_pow(ll a,ll n) {
    ll base = a;
    ll ret =1;

    for( ;n ;n=n >> 1){
        if(n & 1)//取最低位, 是不是很像判断奇偶
            ret = ret * base % mod;
        base = base*base % mod;
    }

    return ret % mod;
}

signed main (int argc, char *argv[]) {
    ios::sync_with_stdio(false); cin.tie(0);
    init();

    for(int i = n;i-2 >= 0;i--) {
        cnt[i-2] += cnt[i];
        // std::cout << i << " " << cnt[i] <<endl;
    }

    ll ans = 1;
    for(int i = n;i >= 1;i--) {
        // 快速密
        if( i % 2 == 1) {
            if( k >= cnt[i]) {
                ans *= quick_pow(i,cnt[i]);
                ans %= mod;
                k-=cnt[i];
            }
            else if ( k != 0){
                ans *= quick_pow(i,k);
                ans %= mod;
                k = 0;
                break;
            }

        }
    }
    if( k != 0){
        std::cout << -1 << "\n";
    }
    else
        std::cout << ans << "\n";
    
    return 0;
}