专栏文章

P7758 题解

GGuizy
P7758题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio60v0p
此快照首次捕获于
2025/12/02 13:56
3 个月前
此快照最后确认于
2025/12/02 13:56
3 个月前
查看原文

题目大意

给你 nn 个字符串，求合法排列的方案数。
一个排列是合法的，当且仅当所有有相同前缀的字符串在排行榜上相邻。

做法

模拟赛赛时的思路。
考虑手玩样例 2：
CPP
MARICA
MARTA
MATO
MARA
MARTINA
先排个序，反正对答案没影响：
CPP
MARA
MARICA
MARTA
MARTINA
MATO
然后发现 MARTA 和 MARTINA 之间可以任意交换，答案乘上 2!2!。
同样的，只要保证 MARTA 和 MARTINA 相邻，MARA，MARICA，MARTA，MARTINA 之间也可以任意交换。
我们不妨把 MARTA 和 MARTINA 看做一个字符串。所以方案数是 3!3!，乘到答案中。
同理最后 MATO 和前四个字符串也是任意交换，答案乘上 2!2!。
所以最后 ansans 就等于 2!×3!×2!=242!\times 3!\times 2! = 24。
到这里，想必你也已经会了个大概了。下面的我就先折叠，大家可以自己想一想。
最终解法
我们直接模拟这个过程。
先对这些字符串排序。
用一个栈维护这些字符串的 LCP。
每次遇到相同的 LCP 就合并。
遇到不同的，分类讨论 LCP 是变大了还是变小了。
如果变大了，就直接把新的 LCP 入栈，否则就统计答案后将原 LCP 出栈，新 LCP 入栈。
可能这样讲还是不太清楚，那就看代码吧。
赛时代码
有些地方赛时写的比较保守，欢迎提出更好的写法。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...