$\large{\textrm{Description}}$

给定一个长度为 $n$ 的字符串。

要求在 $O(n)$ 的时间复杂度之内求出它的最长回文子串的长度。

$\large{\textrm{Solution}}$

首先将整个字符串中任意两个位置间插入字符 # （左右两端也要加上不同字符防止越界）。

例如原先是

a b c b a

处理后变为

$ # a # b # c # b # a # %

这样处理使得原串中的任意回文串在后串中都表示为奇数长度串的形式，且都有一个中心点。

设 $p_i$ 表示为以 $i$ 为中心点的最大半径（右端点到中心点的串的长度，包括两端）。

从左向右扫描每一个 $i$ ，

• 已知 $i$ 之前的所有回文串中右端点最靠右的串的中心点 $m$ 以及右端点 $r$ 。

• 若 $i \leq r$ ，设初始 $p_i = p_{2m - i}$（$2m-i$ 为 $i$ 在此串上的对称点）；否则设初始 $p_i = 1$ 。

• 不断扩大边界，若 $s_{i - p_i} = s_{i+p_i}$ 成立，$p_i$ 加一。

• 判断 $i + p_i - 1$ 是否大于 $r$ ，更新 $m$ 和 $r$ 。

$\large{\textrm{Time complexity}}$

每一个点都被扫过一次，时间复杂度 $O(n)$ 。

$\large{\textrm{Code}}$

#include <bits/stdc++.h>
using namespace std;

const int N = 2e7 + 10;
int n;
char a[N], b[N];
int p[N];

void init() {
    int k = 0;
    b[k ++ ] = '$', b[k ++ ] = '#';
    for (int i = 0; i < n; i ++ ) b[k ++ ] = a[i], b[k ++ ] = '#';
    b[k ++ ] = '^';
    n = k;
}

void manacher() {
    int mr = 0, mid;
    for (int i = 0; i < n; i ++ ) {
        if (i < mr) p[i] = min(p[mid + mid - i], mr - i);
        else p[i] = 1;
        while (b[i - p[i]] == b[i + p[i]]) p[i] ++ ;
        if (i + p[i] > mr) {
            mr = i + p[i];
            mid = i;
        }
    }
}

int main() {
    scanf("%s", a);
    n = strlen(a);
    init();
    manacher();
    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, p[i] - 1);
    printf("%d", res);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1000010, P = 1e9 + 7;
int p[N], tot;
int mu[N], fib[N], inv[N];
int g[N], g_inv[N];
bool vis[N];

int power(int a, LL b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % P;
        a = 1ll * a * a % P;
        b >>= 1;
    }
    return res;
}

void get_mu(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; i ++ ) {
        if (!vis[i]) {
            p[++ tot] = i;
            mu[i] = -1;
        }
        for (int j = 1; p[j] * i <= n; j ++ ) {
            vis[p[j] * i] = true;
            if (i % p[j] == 0) {
                mu[p[j] * i] = 0;
                break;
            }
            mu[p[j] * i] = -mu[i];
        }
    }
}

void get_fib(int n) {
    inv[0] = fib[1] = 1;
    for (int i = 2; i <= n; i ++ ) fib[i] = (fib[i - 1] + fib[i - 2]) % P;
    for (int i = 1; i <= n; i ++ ) inv[i] = power(fib[i], P - 2);
}

void get_g(int n) {
    g_inv[0] = 1;
    for (int i = 0; i <= n; i ++ ) g[i] = 1;
    for (int d = 1; d <= n; d ++ )
        for (int T = d; T <= n; T += d) {
            if (mu[T / d] == 1) g[T] = 1ll * g[T] * fib[d] % P;
            else if (mu[T / d] == -1) g[T] = 1ll * g[T] * inv[d] % P;
        }
    for (int i = 1; i <= n; i ++ ) g[i] = 1ll * g[i - 1] * g[i] % P;
    for (int i = 1; i <= n; i ++ ) g_inv[i] = power(g[i], P - 2);
}

int main()
{
    get_mu(1e6);
    get_fib(1e6);
    get_g(1e6);

    int T;
    scanf("%d", &T);
    while (T -- ) {
        int n, m;
        scanf("%d%d", &n, &m);
        if (n > m) swap(n, m);

        int ans = 1;
        for (int l = 1, r; l <= n; l = r + 1) {
            r = min(n / (n / l), m / (m / l));
            ans = 1ll * ans * power(1ll * g[r] * g_inv[l - 1] % P, 1ll * (n / l) * (m / l)) % P;
        }

        printf("%d\n", ans);
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 2000010, M = 410, P = (1 << 19) - 1;
int n, m;
int tr[M][30], tot;
int ne[M], l[M], g[N];
char str[N];
bool End[M], f[N];

void insert() {
    int p = 0, len = strlen(str);
    for (int i = 0; i < len; i ++ ) {
        int c = str[i] - 'a';
        if (!tr[p][c]) tr[p][c] = ++ tot;
        p = tr[p][c];
    }
    End[p] = true;
}

void build() {
    queue<int> q;
    for (int i = 0; i < 26; i ++ )
        if (tr[0][i])
            q.push(tr[0][i]);

    while (q.size()) {
        int t = q.front();
        g[t] = g[ne[t]] | (End[t] ? (1 << l[t]) : 0);
        q.pop();
        for (int i = 0; i < 26; i ++ ) {
            int np = tr[t][i];
            if (!np) tr[t][i] = tr[ne[t]][i];
            else {
                l[np] = l[t] + 1;
                ne[np] = tr[ne[t]][i];
                q.push(np);
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ ) {
        scanf("%s", str);
        insert();
    }

    build();

    while (m -- ) {
        scanf("%s", str + 1);
        int len = strlen(str + 1);
        int x = 1, res = 0;
        for (int i = 1, p = 0; i <= len; i ++ ) {
            int c = str[i] - 'a';
            p = tr[p][c];
            if (g[p] & x) f[i] = 1, res= i;
            else f[i] = 0;
            x = (x * 2 + f[i]) & P;
        }
        printf("%d\n", res);
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int P = 19940417, inv6 = 3323403;

int calc(int x) {
    return 1ll * x * (x + 1) % P * (2 * x + 1) % P * inv6 % P;
}

int f(LL n, LL limit) {
    int ans = 0;
    for (int l = 1, r; l <= limit; l = r + 1) {
        r = min(limit, n / (n / l));
        ans = (ans + 1ll * (l + r) * (r - l + 1) / 2 % P * (n / l) % P) % P;
    }
    return ans;
}

int g(int n, int m) {
    int ans = 0;
    for (int l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        ans = (ans + 1ll * (calc(r) + P - calc(l - 1)) % P * (n / l) % P * (m / l) % P) % P;
    }
    return ans;
}

int h(int x) {
    return (1ll * x * x % P + P - f(x, x)) % P;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    if (n > m) swap(n, m);
    printf("%d", (1ll * h(n) * h(m) % P + P - 1ll * n * n % P * m % P + 1ll * m * f(n, n) % P + 1ll * n * f(m, n) % P + P - g(n, m)) % P);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
int n, p;
int prime[8] = {2, 3, 5, 7, 11, 13, 17, 19};
int dp1[N][N], dp2[N][N], dp[N][N], v[N];
pair<int, int> e[N];

int main() {
    scanf("%d%d", &n, &p);

    for (int i = 1; i < n; i ++ ) {
        int j = i + 1;
        for (int k = 0; k < 8; k ++ ) {
            if (j % prime[k] == 0) v[i] |= (1 << k);
            while (j % prime[k] == 0) j /= prime[k];
        }
        e[i] = {j, i};
    }

    sort(e + 1, e + n);

    dp[0][0] = 1;
    for (int i = 1, l = 1; i < n; i ++ )
        if (e[i + 1].first != e[i].first || e[i].first == 1) {
            memcpy(dp1, dp, sizeof(dp));
            memcpy(dp2, dp, sizeof(dp));
            for (int j = l; j <= i; j ++ )
                for (int L = 255; L >= 0; L -- )
                    for (int R = 255; R >= 0; R -- ) {
                        if (!(v[e[j].second] & R)) dp1[L | v[e[j].second]][R] = (dp1[L | v[e[j].second]][R] + dp1[L][R]) % p;
                        if (!(v[e[j].second] & L)) dp2[L][R | v[e[j].second]] = (dp2[L][R | v[e[j].second]] + dp2[L][R]) % p;
                    }
            for (int L = 0; L < 256; L ++ )
                for (int R = 0; R < 256; R ++ )
                    dp[L][R] = ((dp1[L][R] + dp2[L][R]) % p - dp[L][R] + p) % p;
            l = i + 1;
        }

    int ans = 0;
    for (int L = 0; L < 256; L ++ )
        for (int R = 0; R < 256; R ++ )
            ans = (ans + dp[L][R]) % p;

    printf("%d", ans);

    return 0;
}

凸包

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;
const int N = 1010;
const double Pi = 3.141592654;
int n, L;
int q[N];
PDD a[N];

double cross(double x1, double y1, double x2, double y2)
{
    return x1 * y2 - x2 * y1;
}

double area(PDD a, PDD b, PDD c)
{
    return cross(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}

double Andrew()
{
    double res = 0;
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i ++ )
    {
        while (hh < tt && area(a[q[tt - 1]], a[q[tt]], a[i]) >= 0) tt -- ;
        q[++ tt] = i;
    }
    for (int i = 1; i <= tt; i ++ )
    {
        double dx = a[q[i]].x - a[q[i - 1]].x, dy = a[q[i]].y - a[q[i - 1]].y;
        res += sqrt(dx * dx + dy * dy);
    }
    hh = 0, tt = -1;
    for (int i = n - 1; i >= 0; i -- )
    {
        while (hh < tt && area(a[q[tt - 1]], a[q[tt]], a[i]) >= 0) tt -- ;
        q[++ tt] = i;
    }
    for (int i = 1; i <= tt; i ++ )
    {
        double dx = a[q[i]].x - a[q[i - 1]].x, dy = a[q[i]].y - a[q[i - 1]].y;
        res += sqrt(dx * dx + dy * dy);
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &L);
    for (int i = 0; i < n; i ++ ) scanf("%lf%lf", &a[i].x, &a[i].y);
    sort(a, a + n);
    printf("%.0lf", Andrew() + Pi * L * 2);
    return 0;
}

$Solution$

现设一个前缀和 $sum$ 和 $rmq$

$sum_i$ 表示 $1\sim i$ 的前缀和。

$f_{i, j}$ 表示 $i$ 前面连续 $2^j$ 个数中最大的 $sum$ 。

$g_{i, j}$ 表示使 $f$ 取到最大值的位置。

对于每一个 $i$ ($1\leq i \leq n$) ，有一个优先队列。

队列中的值形如 $(l, r, val)$ ，表示左端点为 $i$ ，右端点在区间 $[l, r]$ 的中，$val$ 表示以上连续端的最大值。

把所有 $i$ 的优先队列的队头插入全局优先队列中。

每一次取全局队列中的对头，找到它的来源（即 $(l, r, val)$ ）并删除。

再把 $(l, g_{l, r} - 1, val)$ 和 $(g_{l, r} + 1, r, val)$ 插回去。

总时间复杂度 $O(n\log n)$

$Code$

#include <bits/stdc++.h>
using namespace std;

const int N = 500010;
int n, k, L, R;
int a[N];
int f[N][30], g[N][30];

struct GROUP1 {
    int l, r, val;
    bool operator < (const GROUP1 &b) const {
        return val < b.val;
    }   
};

struct GROUP2 {
    int id, val;
    bool operator < (const GROUP2 &b) const {
        return val < b.val;
    }
};

priority_queue<GROUP1> q[N];
priority_queue<GROUP2> heap;

GROUP2 rmq(int l, int r) {
    int len = log2(r - l + 1);
    int a = f[l + (1 << len) - 1][len], b = f[r][len];
    if (a <= b) return {g[r][len], b};
    return {g[l + (1 << len) - 1][len], a};
}

int main() {
    scanf("%d%d%d%d", &n, &k, &L, &R);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]), a[i] += a[i - 1];

    for (int i = 1; i <= n; i ++ ) {
        f[i][0] = a[i], g[i][0] = i;
        for (int j = 1; j < 20; j ++ ) {
            if (i < (1 << j)) break;
            f[i][j] = max(f[i][j - 1], f[i - (1 << j - 1)][j - 1]);
            if (f[i][j] == f[i][j - 1]) g[i][j] = g[i][j - 1];
            else g[i][j] = g[i - (1 << j - 1)][j - 1];
        }
    }

    for (int i = 1; i <= n - L + 1; i ++ ) {
        int LL = i + L - 1, RR = min(i + R - 1, n);
        int v = rmq(LL, RR).val - a[i - 1];
        q[i].push({LL, RR, v});
        heap.push({i, v});
    }

    long long res = 0;
    while (k -- ) {
        auto t = heap.top();
        heap.pop();
        res += t.val;
        auto p = q[t.id].top();
        q[t.id].pop();
        int d = rmq(p.l, p.r).id;
        if (p.l <= d - 1) q[t.id].push({p.l, d - 1, rmq(p.l, d - 1).val - a[t.id - 1]});
        if (d + 1 <= p.r) q[t.id].push({d + 1, p.r, rmq(d + 1, p.r).val - a[t.id - 1]});
        if (q[t.id].size())heap.push({t.id, q[t.id].top().val});
    }

    printf("%lld", res);

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 210, M = 410, INF = 0x3f3f3f3f;
map<int, int> ha;
int s[N], t[N], T[M], tot;
int v[M][M], f[M][N], g[M][N];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) {
        scanf("%d%d", &s[i], &t[i]);
        t[i] += s[i];
        T[++ tot] = s[i], T[++ tot] = t[i];
    }

    sort(T + 1, T + tot + 1);
    int m = unique(T + 1, T + tot + 1) - (T + 1);
    for (int i = 1; i <= m; i ++ ) ha[T[i]] = i;
    for (int i = 1; i <= n; i ++ ) s[i] = ha[s[i]], t[i] = ha[t[i]];

    for (int i = 1; i <= m; i ++ )
        for (int j = i + 1; j <= m; j ++ )
            for (int k = 1; k <= n; k ++ )
                if (s[k] >= i && t[k] <= j)
                    v[i][j] ++ ;

    for (int i = 1; i <= m; i ++ )
        for (int j = 0; j <= n; j ++ ) {
            f[i][j] = -INF;
            if (j == 0) f[i][j] = v[1][i];
            for (int k = 1; k < i; k ++ ) {
                f[i][j] = max(f[i][j], f[k][j] + v[k][i]);
                f[i][j] = max(f[i][j], f[k][max(0, j - v[k][i])]);
            }

        }

    for (int i = m; i >= 1; i -- )
        for (int j = n; j >= 0; j -- ) {
            g[i][j] = -INF;
            if (j == 0) g[i][j] = v[i][m];
            for (int k = m; k > i; k -- ) {
                g[i][j] = max(g[i][j], g[k][j] + v[i][k]);
                g[i][j] = max(g[i][j], g[k][max(0, j - v[i][k])]);
            }
        }

    int r = 0;
    for (int i = 1; i <= n; i ++ ) r = max(r, min(f[m][i], i));
    printf("%d\n", r);

    for (int i = 1; i <= n; i ++ ) {
        int res = 0;
        for (int l = 1; l <= s[i]; l ++ )
            for (int r = t[i]; r <= m; r ++ ) {
                for (int j = 0; j <= v[1][l]; j ++ ) {
                    for (int k = 0; k <= v[r][m]; k ++ ) {
                        res = max(res, min(j + k + v[l][r], f[l][j] + g[r][k]));
                        if (g[r][k] < k) break;
                    }
                    if (f[l][j] < j) break;
                }
                if (v[1][l] + v[r][m] < res) break;
                if (v[l][r] > v[1][l] + v[r][m]) break;
            }
        printf("%d\n", res);
    }

    return 0;
}

$Part1$

对于每一个字符串而言，当它经过栈里括号匹配后剩下的一定为形如左边一堆 ) 右边一堆 ( 的串。

) ... ) ) ( ( ... (

若左右括号数量相等，这个串可以通过一次变换操作匹配

由于字符串内的左右括号数量差异是不得不补的，设左括号 $a$ 个，右括号 $b$ 个。

由于前 $|a - b|$ 个括号是一定要填的，而填完后只有两个选择，变换或不变。

当天完后 $a$ 或 $b$ 其中一个为 $0$ ，则可以不变换，否则要换。

一个简明的思路是枚举从 $i$ 开头的串，依次将 $i\sim n$ 加入栈中并统计答案。

时间复杂度 $O(n^2)$ 。

提交记录

$Part2$

一个复杂的 $dp$ .

用树状数组提前求出 $low_i$ 表示以 $i$ 结尾的所有字符串中左括号数严格小于右括号数的个数。

设 $f_i$ 为以 $i$ 结尾的前缀字符串的左括号数减去右括号数，则

$$low_i = \sum_{j = 1}^i [f_i - f_{j - 1} < 0]$$

$$low_i = \sum_{j = 1}^i [f_{j-1}>f_i]$$

由于 $f$ 可能为负数，需要事先加上一个大整数。

$res_i$ 表示以 $i$ 结尾的字符串答案之和。

$cnt0_i$ 表示以 $i$ 结尾的字符串经过括号匹配后无左括号且有右括号。

$cnt1_i$ 表示以 $i$ 结尾的字符串经过括号匹配后无右括号且有左括号。

$both_i$ 表示以 $i$ 结尾的字符串经过括号匹配后无左括号和右括号。

$g_i$ 表示前缀串 $i$ 的最靠右的点 $j$ ，满足 $j$ 上为 ( 且 $(j+n,i)$ 为合法区间 （可空）。

转移方程：

if (str[i] == '(') {
    res[i] = res[i - 1] - low[i - 1] + i - low[i - 1] + cnt0[i - 1];
    cnt1[i] = cnt1[i - 1] + both[i - 1] + 1;
    g[i] = i;
} 
else {
    if (g[i - 1] == 0) {
        res[i] = res[i - 1] + i;
        cnt0[i] = cnt0[i - 1] + both[i - 1] + 1;
        both[i] = g[i] = 0;
    } 
    else {
        int o = i - 1, h = g[o] - 1;
        res[i] = res[h] + res[o] - res[g[o]] + i - g[i - 1];
        cnt0[i] = cnt0[h] + i - g[o];
        cnt1[i] = cnt1[h];
        both[i] = both[h] + 1;
        g[i] = g[h];
    }
}

最终时间复杂度 $O(n\log n)$ （瓶颈在于树状数组），卡常即可过。

$实现$

提交记录

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 2000010;
int n, M;
LL res[N];
int f[N], g[N], tr[2 * N];
int cnt0[N], cnt1[N], both[N];
int low[N];
char str[N];

inline int lowbit(int x) {
    return x & -x;
}

inline void add(int x, int k) {
    x = M - x + 1;
    for (int i = x; i <= M; i += lowbit(i)) tr[i] += k;
}

inline int sum(int x) {
    x = M - x + 1;
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

inline void clean() {
    for (int i = 1; i <= n; ++ i ) res[i] = g[i] = cnt0[i] = cnt1[i] = both[i] = 0;
    for (int i = 0; i <= n; ++ i ) add(f[i], -1), f[i] = 0;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T -- ) {
        scanf("%d%s", &n, str + 1);

        M = 2 * n + 1;
        for (register int i = 1; i <= n; ++ i)
            if (str[i] == '(') f[i] = f[i - 1] + 1;
            else f[i] = f[i - 1] - 1;

        for (register int i = 0; i <= n; ++ i ) f[i] += n + 1;

        add(f[0], 1);
        for (register int i = 1; i <= n; ++ i ) {
            low[i] = sum(f[i] + 1);
            add(f[i], 1);
        }

        long long ans = 0;
        for (register int i = 1; i <= n; ++ i ) {
            if (str[i] == '(') {
                res[i] = res[i - 1] - low[i - 1] + i - low[i - 1] + cnt0[i - 1];
                cnt1[i] = cnt1[i - 1] + both[i - 1] + 1;
                g[i] = i;
            } else {
                if (g[i - 1] == 0) {
                    res[i] = res[i - 1] + i;
                    cnt0[i] = cnt0[i - 1] + both[i - 1] + 1;
                    both[i] = g[i] = 0;
                } else {
                    register int o = i - 1, h = g[o] - 1;
                    res[i] = res[h] + res[o] - res[g[o]] + i - g[i - 1];
                    cnt0[i] = cnt0[h] + i - g[o], cnt1[i] = cnt1[h], both[i] = both[h] + 1;
                    g[i] = g[h];
                }
            }
            ans += res[i];
        }
        printf("%lld\n", ans);
        clean();
    }
    return 0;
}

$四边形不等式$

已知二元函数 $f(n, m)$ ，若

$\forall a, b, c, d,$ 且 $a\leq b\leq c \leq d$ 都有 $f(a, d) + f(b, d) \ge f(a, c) + f(b, d)$

则称 $f$ 函数满足四边形不等式。

$四边形不等式的判定$

• 对于所有满足 $a\leq b\leq c \leq d$ 的正整数 $a, b, c, d$ 有 $f(a, d) + f(b, d) \ge f(a, c) + f(b, d)$

• 对于所有满足 $i < j$ 的正整数 $i, j$ 有 $f(i, j + 1) + f(i + 1, j) \ge f(i, j) + f(i + 1, j + 1)$

$四边形不等式优化$

四边形不等式应用于 $\textrm{dp}$ 中，若转移方程形如：

$$f_i = \min_{j = 1}^{i - 1} f_j + V_{j, i}$$

且 $V$ 函数满足四边形不等式，那么 $f$ 具有决策单调性。

「决策单调性」

若位置 $p$ 对于 $i$ 而言满足 $\forall j < p , f_j + V_{j, i} \ge f_p + V_{p, i}$

那么对于所有 $i’ > i$ 的所有位置而言也满足 $\forall j < p , f_j + V_{j, i’} \ge f_p + V_{p, i’}$

证明：

已知 $V$ 满足四边形不等式，即

$$V_{j, i’} + V_{p, i} \ge V_{j, i} + V_{p, i’}$$

又由于满足

$$ f_j + V_{j, i} \ge f_p + V_{p, i}$$

将两个不等式相加，得

$$f_j + V_{j, i’} \ge f_p + V_{p, i’}$$

证毕

由此得出结论，若 $p_i$ 表示为 $f_i$ 决策时最优秀的 $j$ ，那么 $p_i$ 非严格单调递增。

$实现$

以 「诗人小 $G$ 」为例。

#include <bits/stdc++.h>
using namespace std;

typedef long double LD;
const int N = 100010;
int n, L, P, hh, tt;
int s[N], opt[N];
LD f[N];
char str[N][40];

struct Node {
    int j, l, r;
} q[N];

LD val(int j, int i) {
    LD res = 1, t = abs(s[i] - s[j] + i - j - 1 - L);
    for (int i = 0; i < P; i ++ ) res *= t;
    return res + f[j];
}

void insert(int i) {
    int pos = n + 1;
    while (hh <= tt && val(q[tt].j, q[tt].l) >= val(i, q[tt].l)) pos = q[tt -- ].l;
    if (hh <= tt && val(q[tt].j, q[tt].r) >= val(i, q[tt].r)) {
        int l = q[tt].l, r = q[tt].r;
        while (l < r) {
            int mid = l + r >> 1;
            if (val(q[tt].j, mid) >= val(i, mid)) r = mid;
            else l = mid + 1;
        }
        pos = l;
        q[tt].r = l - 1;
    }
    if (pos != n + 1) q[++ tt] = {i, pos, n};
}

int main() {
    int T;
    scanf("%d", &T);
    while (T -- ) {
        scanf("%d%d%d", &n, &L, &P);
        for (int i = n; i >= 1; i -- ) scanf("%s", str[i]);
        for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + strlen(str[i]);
        hh = tt = 0;
        q[0] = {0, 1, n};
        for (int i = 1; i <= n; i ++ ) {
            f[i] = val(q[hh].j, i), opt[i] = q[hh].j;
            if (q[hh].r == i) hh ++ ;
            q[hh].l = i + 1;
            insert(i);
        }
        if (f[n] > 1e18) puts("Too hard to arrange");
        else {
            printf("%lld\n", (long long)f[n]);
            for (int i = n; i; i = opt[i])
            {
                for (int j = i; j > opt[i]; j -- )
                {
                    printf("%s", str[j]);
                    if (j != opt[i] + 1) printf(" ");
                }
                puts("");
            }
        }
        puts("--------------------");
    }
    return 0;
}