P7758 题解

· · 题解

题目大意

给你 n 个字符串，求合法排列的方案数。

一个排列是合法的，当且仅当所有有相同前缀的字符串在排行榜上相邻。

做法

模拟赛赛时的思路。

考虑手玩样例 2：

MARICA
MARTA
MATO
MARA
MARTINA

先排个序，反正对答案没影响：

MARA
MARICA
MARTA
MARTINA
MATO

然后发现 MARTA 和 MARTINA 之间可以任意交换，答案乘上 2!。

同样的，只要保证 MARTA 和 MARTINA 相邻，MARA，MARICA，MARTA，MARTINA 之间也可以任意交换。

我们不妨把 MARTA 和 MARTINA 看做一个字符串。所以方案数是 3!，乘到答案中。

同理最后 MATO 和前四个字符串也是任意交换，答案乘上 2!。

所以最后 ans 就等于 2!\times 3!\times 2! = 24。

到这里，想必你也已经会了个大概了。下面的我就先折叠，大家可以自己想一想。

::::info[最终解法] 我们直接模拟这个过程。

先对这些字符串排序。

用一个栈维护这些字符串的 LCP。

每次遇到相同的 LCP 就合并。

遇到不同的，分类讨论 LCP 是变大了还是变小了。

如果变大了，就直接把新的 LCP 入栈，否则就统计答案后将原 LCP 出栈，新 LCP 入栈。

可能这样讲还是不太清楚，那就看代码吧。 :::: ::::info[赛时代码] 有些地方赛时写的比较保守，欢迎提出更好的写法。

#include<bits/stdc++.h>
#define int long long
#define r(x) for (int i = 1; i <= x; i++)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define reb(i, a, b) for (int i = a; i >= b; i--)
using namespace std;

const int N = 3050, P = 1e9 + 7;
int n, ans = 1, p[N], f[N];
// p[x] 表示 x 在栈中出现几次 
string s[N];
stack<int> st;

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n, f[0] = 1;
    r(n) cin >> s[i];
    r(N - 10) f[i] = (f[i - 1] * i) % P; //预处理阶乘 
    sort(s + 1, s + n + 1); //排序 
    int len = min(s[1].size(), s[2].size()), k = len;
    rep(j, 0, len - 1)
        if (s[1][j] != s[2][j])
            { k = j; break; }
    //先处理前两个的 lcp 
    rep(i, 0, k) st.push(i), p[i]++;
    //按手玩的方法模拟 
    rep(i, 2, n)
    {
        int len = min(s[i].size(), s[i - 1].size()), k = len;
        rep(j, 0, len - 1) 
            if (s[i][j] != s[i - 1][j])
                { k = j; break; }
        //计算 lcp 
        int t = 0, tp;
        if (!st.empty()) t = st.top(); //防 RE 
        if (t >= k)
        {
            reb(j, t, k + 1)
            {
                tp = st.top(), st.pop();
                ans = (ans * f[p[tp]]) % P;
                // 统计答案，这里就表示有 p[tp] 个 lcp 为 tp 的， 
                // 贡献自然就是 f[p[tp]]，乘到答案里。
                p[tp] = 0; 
            } p[k]++; //因为栈顶已经是 k，所以不用 push。 
        }
        else
        {
            rep(j, t + 1, k - 1)
                st.push(j), p[j]++;
            st.push(k), p[k] = 2;
            // 因为当前其实已经有 2 个 lcp 为 k 的
            // 所以 p[k] 初始化为 2 
        }
    }
    while (!st.empty())
    {
        int tp = st.top();
        st.pop(), ans = (ans * f[p[tp]]) % P;
        // 以防万一，可能不加这个 while 也可以 
    }
    cout << ans << "\n"; 
    return 0;
}

::::