P7758 [COCI2012-2013#3] HERKABE 题解

Untitled_unrevised · 2023-02-20 05:30:26 · 题解

题目分析

「……所以他决定有相同前缀的名字必须在名单上彼此相邻。……对于名单上每两个有相同前缀的名字，在排行榜上他们之间的所有名字也应当有这一个前缀。」

换句话说就是，前缀相同的必须分到一组去。

作为一个简单的例子，样例 1 就需要这么分组：

IVO, {JASNA, JOSIPA}

但对于样例 2，有的字符串有更长的公共前缀，就应该这么分组：

{
    (LCP = "MA")
    {
        (LCP = "MAR")
        MARA,
        MARICA,
        {
            (LCP = "MART")
            MARTA,
            MARTINA
        }
    },
    MATO
}

其中 LCP 指 Longest Common Prefix，最长公共前缀。

分组方法

如果你知道字典树的话，最直接的做法就是逐一插入字符串，这样就可以将具有最长公共前缀 s 的字符串都放到以字符串 s 的节点为根的子树下。

但是这题的空间限制是 32 MB，使用字典树对于最后 3 个数据点会 MLE。

一种更节省空间的做法，基于 MSD 型基数排序（从高位到低位比较的基数排序）：

首先枚举公共前缀（注意不用是最长的公共前缀）的长度 |\mathrm{CP}| 为 1，此时 \mathrm{CP} \in \{\mathtt{"A"}, \mathtt{"B"}, \dots, \mathtt{"Z"}\}。将具有相同 \mathrm{CP} 的字符串分到同一组。

对于每一组，再令 |\mathrm{CP}| = 2，比如对于上一次分组已经分到 \mathrm{CP} = \mathtt{"A"} 的，此时 \mathrm{CP} \in \{\mathtt{"AA"}, \mathtt{"AB"}, \dots, \mathtt{"AZ"}\}，再接着将具有相同 \mathrm{CP} 的字符串分到同一组。

……

重复上述过程，直至每组只剩一个字符串。

注意：

使用 MSD 型基数排序进行分组后，一定要把字符串倒回原数组，否则一次递归都会不得不创建存储分组情况的数组，一样有可能 MLE；
存储分组情况的数组不要放在执行递归操作的函数里，原因同 1。可以将这个数组设为全局。
直接交换字符串的时间复杂度是线性的，建议只交换指向字符串的指针或引用。

参考代码：

typedef char * mystr;
const size_t MAXBUCKET = 27;
std::queue<mystr> bucket[MAXBUCKET];

// [first, last) 里的元素是指向每个字符串的指针
// offset 表示访问每个字符串的第 offset 个字符
void MSD_radix_sort(mystr *first, mystr *last, size_t offset = 0) {

    // 如果只剩一个字符串，直接返回
    if(last - first == 1)
        return;

    // 分组，存储到 bucket 里
    for(mystr *ptr = first; ptr != last; ++ptr) {
        char ch = (*ptr)[offset];
        int idx = ch ? ch - '@' : 0; // 此处是将 C 风格字符串中的 '\0' 映射到 0，'A' ~ 'Z' 映射到 1 ~ 26
        bucket[idx].push(*ptr);
    }

    // 倒回原数组，borders 是每组的边界
    mystr *ptr = first;
    mystr *borders[MAXBUCKET + 1] = {first};
    for(int idx = 0; idx < MAXBUCKET; ++idx) {
        while(!bucket[idx].empty()) {
            *ptr++ = bucket[idx].front();
            bucket[idx].pop();
        }
        borders[idx+1] = ptr;
    }

    // 递归分组
    for(int idx = 0; idx < MAXBUCKET; ++idx)
        if(borders[idx+1] != borders[idx])
            MSD_radix_sort(borders[idx], borders[idx+1], offset+1);

}

求方案数

分组完之后，如何求方案数呢？

根据题目，同一个组的字符串必须相邻，但是顺序可以随意调换。

以样例 1 为例：

对于 IVO 和 {JASNA, JOSIPA} 这 2 组字符串，它们可以自由决定先后顺序，有 2! = 2 种排法：

#1:
IVO
{JASNA, JOSIPA}

#2:
{JASNA, JOSIPA}
IVO

对于 JASNA, JOSIPA 这组字符串，还有 2! = 2 种排法：

#1:
JASNA
JOSIPA

#2
JOSIPA
JASNA

综上，样例 1 的方案数是 2! \times 2! = 4。

再以样例 2 为例：

对于 {MARICA, MARA, {MARTA, MARTINA}} 和 MATO 这 2 组字符串，有 2! = 2 种排法：

#1
{MARICA, MARA, {MARTA, MARTINA}}
MATO

#2
MATO
{MARICA, MARA, {MARTA, MARTINA}}

对于 MARICA, MARA, {MARTA, MARTINA} 这 3 组字符串，有 3! = 6 种排法：

#1:
MARICA
MARA
{MARTA, MARTINA}

...

#6:
{MARTA, MARTINA}
MARA
MARICA

对于 MARTA, MARTINA 这组字符串，有 2! = 2 种排法。

综上，样例 2 有 2! \times 2! \times 3! = 24 种排法。

以上计算过程可以边分组边计算：

假设待分组的字符串集合为 S，求方案数 f(S)；

当具有相同 \mathrm{CP} 的字符串分到第 i 组 T_i 后：

f(S) = n![f(T_1)f(T_2)\dots f(T_n)] = n!\prod_{i = 1}^{n}f(T_i)

其中 n 是非空的 T_i 个数。

递归终点：当 |T| = 1 时，f(T) = 1。（只有一个字符串也有 1 种排法）

在基数排序代码的基础上进行修改即可，返回值就是当前组能产生的方案数：

const long long P = 1000000007;
const long long fact[28] = {
    1, 1, 2, 6, 24,
    120, 720, 5040, 40320, 362880,
    3628800, 39916800, 479001600, 227020758, 178290591,
    674358851, 789741546, 425606191, 660911389, 557316307,
    146326063, 72847302, 602640637, 860734560, 657629300,
    440732388, 459042011, 394134213
};

typedef char * mystr;
const size_t MAXBUCKET = 27;
std::queue<mystr> bucket[MAXBUCKET];

// [first, last) 里的元素是指向每个字符串的指针
// offset 表示访问每个字符串的第 offset 个字符
long long MSD_radix_sort(mystr *first, mystr *last, size_t offset = 0) {

    // 如果只剩一个字符串，返回方案数 1
    if(last - first == 1)
        return 1ll;

    // 分组，存储到 bucket 里
    for(mystr *ptr = first; ptr != last; ++ptr) {
        char ch = (*ptr)[offset];
        int idx = ch ? ch - '@' : 0; // 此处是将 C 风格字符串中的 '\0' 映射到 0，'A' ~ 'Z' 映射到 1 ~ 26
        bucket[idx].push(*ptr);
    }

    // 倒回原数组，borders 是每组的边界
    mystr *ptr = first;
    mystr *borders[MAXBUCKET + 1] = {first};
    for(int idx = 0; idx < MAXBUCKET; ++idx) {
        while(!bucket[idx].empty()) {
            *ptr++ = bucket[idx].front();
            bucket[idx].pop();
        }
        borders[idx+1] = ptr;
    }

    // res 记录答案，branch 记录非空子集数
    long long res = 1, branch = 0;  

    // 递归分组
    for(int idx = 0; idx < MAXBUCKET; ++idx) {
        if(borders[idx+1] != borders[idx]) {
            res = res * MSD_radix_sort(borders[idx], borders[idx+1], offset+1) % P;
            ++branch;
        }
    }

    return res * fact[branch] % P;

}

完整的参考代码如下：

#include <stdio.h>
#include <queue>

const long long P = 1000000007;
const long long fact[28] = {
    1, 1, 2, 6, 24,
    120, 720, 5040, 40320, 362880,
    3628800, 39916800, 479001600, 227020758, 178290591,
    674358851, 789741546, 425606191, 660911389, 557316307,
    146326063, 72847302, 602640637, 860734560, 657629300,
    440732388, 459042011, 394134213
};

typedef char * mystr;
const size_t MAXBUCKET = 27;
std::queue<mystr> bucket[MAXBUCKET];

long long MSD_radix_sort(mystr *first, mystr *last, size_t offset = 0) {

    if(last - first == 1)
        return 1ll;

    for(mystr *ptr = first; ptr != last; ++ptr) {
        char ch = (*ptr)[offset];
        int idx = ch ? ch - '@' : 0;
        bucket[idx].push(*ptr);
    }

    mystr *ptr = first;
    mystr *borders[MAXBUCKET + 1] = {first};
    for(int idx = 0; idx < MAXBUCKET; ++idx) {
        while(!bucket[idx].empty()) {
            *ptr++ = bucket[idx].front();
            bucket[idx].pop();
        }
        borders[idx+1] = ptr;
    }

    long long res = 1, branch = 0;

    for(int idx = 0; idx < MAXBUCKET; ++idx) {
        if(borders[idx+1] != borders[idx]) {
            res = res * MSD_radix_sort(borders[idx], borders[idx+1], offset+1) % P;
            ++branch;
        }
    }

    return res * fact[branch] % P;

}

int main() {

    int n;
    scanf("%d", &n);
    char str[3000][3001] = {};
    mystr strptrs[3000] = {};

    for(int i = 0; i < n; ++i) {
        scanf("%s", str[i]);
        strptrs[i] = str[i];
    }

    printf("%lld", MSD_radix_sort(strptrs, strptrs + n));

    return 0;

}