自动搬运

查看原文

来自洛谷，原作者为

	i262303 人活着就是为了胡桃嘛！！！

搬运于2025-08-24 22:32:49，当前版本为作者最后更新于2022-07-15 21:27:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面传送门

首先，Herkabe 老师要把前缀相同的放在一起，本蒟蒻选择采用sort的方式（大佬有更好的方法可以留言）

然后，我们就成功地将 $n$ 个字符串分成第一个字符相同的 $m$ 组字符串

对于求 $m$ 组字符串的排列数 ，其实很简单。

我们定义 $f_i$ 为第 $i$ 组字符串的排列数，那么 $m$ 组字符串的排列数就是 $(\prod_{i=1}^m f_i)\cdot m!$

那么我们只要求出每一组字符串的方案数，就可以知道答案了。

在上述求 $n$ 个字符串的排列数时，很显然我们用了分治的思想，所以求每一组的方案数我们也可以考虑用分治思想，将一组中的字符串再分为第二个字符相同的几个组，继续分治递归求解，那么我们就可以用分治递归求得最终解。

递归的边界就是当当前组中的字符串数为 $1$ ，返回 $1$ 。

最后给大家康康本蒟蒻丑陋的代码

//我的码风有点奇怪
//加了点卡常的东西
//如：把 ++i 打成 i=-~i ，把 --i 打成 i=~-i
//不过认真看了前面题解的人应该能理解吧
//wjd 666
#include <cstdio>
#include <string>
#include <ctype.h>
#include <iostream>
#include <algorithm>
#define il inline
#define int long long
#define ri register int
using namespace std;
//简简单单的快读快写，其实这题可以不用，只是个人习惯而已
namespace wjd{
	il int read(){
		int x(0);
		char ch(getchar());
		while(!isdigit(ch)) ch=getchar();
		while(isdigit(ch)){
			x=(x<<3)+(x<<1)+(ch&15);
			ch=getchar();
		}
		return x;
	}
	il void write(int x){
		if(x>9) write(x/10);
		putchar((x%10)|48);
	}
}
using namespace wjd;
const int N=3e3+5;
const int MOD=1e9+7;
int fac[N];
string s[N];
//分治递归求解
il int work(int x,int l,int r){
	if((-~l)>=r) return 1;
	ri ll(l),res(1),num(1);
	for(ri i=(-~l);i<r;i=-~i){
		if(s[i][x]==s[ll][x]) continue;
		res=res*work(-~x,ll,i)%MOD;
		ll=i,num=-~num;
	}
	res=res*work(-~x,ll,r)%MOD;
	//最后乘上全排列（阶乘）
	return res*fac[num]%MOD;
}
signed main(){
	int n(read());
	fac[1]=1;
	for(ri i(1);i<=n;i=-~i) cin>>s[i],fac[-~i]=fac[i]*(-~i)%MOD;
	sort(s+1,s+n+1);
	write(work(0,1,-~n));
	return 0;
}

以上就是本蒟蒻对这道灰题的解法，蟹蟹观看 $QAQ$