P7758 [COCI 2012/2013 #3] HERKABE 题解

Hanson2024 · 2025-08-24 15:01:05 · 题解

Link：洛谷

这里介绍两种方法。

方法一

将字符串先排序，那么相邻两两字符串之间肯定有着最长的公共前缀（LCP，Longest Common Prefix）。

设函数 solve(x,l,r) 表示现在要将区间 [l,r] 中字符串分组，依据为第 x 个字符。

那么当 s_i 的第 x 个字符与 s_j 的第 x 个字符不相等时，说明就可以将 i 和 j 分为独立的一组，继续递归求解。

如果最终能被分为 cnt 组，因为这些组之间相互独立，可以任意排列，所以最终乘上 cnt 的阶乘即可。

代码就不放了，题解区里全是。

方法二（人类智慧）

——by cjh

也是一样先排序，意义如上。

那么可以求出相邻两两之间的 LCP 的长度，就像样例二一样：

MARICA MARTA MATO MARA MARTINA

排完序后：

MARA MARICA MARTA MARTINA MATO

求出相邻两两之间的 LCP 的长度：

3 \ 3 \ 4 \ 2 \ 0

后面添上一个 0 的作用等会再说。

设 lcp_i 为 i 和 i+1 的字符串 LCP 的长度。

我们想，现在一个字符串 s_{i+1} 能合法地移动到一个位置 j(i \le j) 的后面，当且仅当：

即：**对于 $i$ 来说**，夹在它中间的 LCP 的长度都要大于它和 $i-1$ 的 LCP 的长度。**注意：不动也是可以的。**
即：$i$ 被夹在 $j$ 和 $j+1$ 中间，也要满足 1 的限制。

举个栗子吧，就比如说将上面的 MARA 插进 MARICA 和 MARTINA 后都是合法的，插进 MATO 和 MARTA 是不合法的。

那么，0 的作用就显而易见了。目的是：为了可以让每个字符串可以插到最后一个字符串的后面。

所以，我们只需要求出对于每一个 i，找出第一个 j(i \le j) 使得 lcp_i > lcp_j。

然后，在区间 [i,j] 中找有多少个 l 满足 lcp_i \le lcp_l 即可，记满足的 l 有 p_i 个。

最终的答案就是 \prod p_i（也是因为相互独立，乘法原理）。

这种方法常数很小，代码也好写。

::::info[代码] Code by cjh

#include<bits/stdc++.h>
#define rint register int
#define LL long long
using namespace std;
const int N=3e3+5,mod=1e9+7;
int a[N];
LL ans=1,cnt;
int n,x;
string s[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(rint i=1;i<=n;++i) cin>>s[i];
    sort(s+1,s+n+1);
    for(rint i=2;i<=n;++i){
        x=min(s[i].size(),s[i-1].size());
        for(rint j=0;j<x;++j){
            if(s[i][j]!=s[i-1][j]) break;
            a[i-1]++;
        }
    }
    for(rint i=1;i<n;++i){
        cnt=0,x=i;
        while(x<=n){
            if(a[x]<=a[i]) ++cnt;
            if(a[x]<a[i]) break;
            x++;
        }
        ans=ans*cnt%mod;
    }
    cout<<ans;
    return 0;
}

::::

P7758 [COCI 2012/2013 #3] HERKABE 题解

方法一

方法二 （人类智慧）

方法二（人类智慧）