题目描述
小x有n个小姊妹(根据典故，我们假设n≤3000)。他每天都喜欢按不同标准给小姊妹们排(da)序(fen)。今天，他突然对小姊妹们的名字产生了兴趣。他觉得小姊妹的魅力和她们的名字有密切联系，于是他觉得所有有相似的名字的小姊妹必须排在一起。
相似是指，名字的开头一个或若干个连续字母相同。
于是，小x定下了如下规则：
在任何以同样的字母序列开头的名字之间，所有名字开头必须是同样的字母序列。
比如，像MARTHA和MARY这两个名字，它们都以MAR开头，所以像MARCO或MARVIN这样的名字可以插入这两个名字中间，而像MAY这样的就不行。
显然，按字典序排序是一个合法的排序方案，但它不是唯一的方案。你的任务就是计算出所有合法的方案数。考虑到答案可能很大，输出答案 mod 1 000 000 007。
输入
第一行一个整数n，小x的小姊妹个数。
第2~n+1行，每行一个字符串，代表这个小姊妹的名字。
输出
一行一个整数，合法的方案数。
样例输入
3
IVO
JASNA
JOSIPA
样例输出
4
数据范围限制
对于60%的数据：3 ≤ n ≤ 10。
对于100%的数据：
3 ≤ n ≤ 3000
1 ≤ 字符串长度 ≤ 3000，并且只含有大写字母。
解题思路
字符数组好难【蒟蒻的bb
先对所有的名字进行补位
for(int i=1;i<=n;i++){
scanf("%s",a[i].aa);
if(strlen(a[i].aa)-1>maxn)maxn=strlen(a[i].aa)-1;
}
for(int i=1;i<=n;i++)
for(int j=strlen(a[i].aa);j<=maxn;j++)
a[i].aa[j]='*';
预先把相似的名字排在一起，字符数组的排序我上网查了好久
bool cmp(const DT&k,const DT&l){
return(strcmp(k.aa,l.aa)<0);
}
sort(a+1,a+n+1,cmp);
方案数：先预处理出来一个s数组，存阶乘。
s[1]=1;
for(int i=2;i<=3000;i++)
s[i]=s[i-1]*i%Mod;
求方案用分治，dfs(x,y,z)表示现在做的是x到y这一些名字的第z位 （ 保证针对前z−1位，x到y这一些名字相等）。
针对z这一位，把x到y这一些名字分成t块，t块可以随意排列，方案ans=s[t]。
每一块又要分治，最后把 每块的方案全部乘起来就好了。
有一种特殊情况，比如x到y这些名字一模一样，那么ans=s[x−y+1]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Mod=1000000007;
struct DT{
char aa[4000];
}a[4000];
int n,maxn;
long long s[4000]={0,1};
void read(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",a[i].aa);
if(strlen(a[i].aa)-1>maxn)maxn=strlen(a[i].aa)-1;
}
for(int i=1;i<=n;i++)
for(int j=strlen(a[i].aa);j<=maxn;j++)
a[i].aa[j]='*';//补位
for(int i=2;i<=3000;i++)
s[i]=s[i-1]*i%Mod;//阶乘
}
bool cmp(const DT&k,const DT&l){
return(strcmp(k.aa,l.aa)<0);
}
long long dfs(int x,int y,int z){
if(z>maxn)return s[y-x+1];//特殊情况
int l=x,t=1;//l是每一块的‘x’
long long ans=1;
for(int i=x+1;i<=y;i++)
if(a[i].aa[z]!=a[l].aa[z]){//如果针对前z位，两个名字不在一块
++t;//块数+1
ans=ans*dfs(l,i-1,z+1)%Mod;//每个块的方案乘在一起
l=i;
}
if(l!=y)ans=ans*dfs(l,y,z+1)%Mod;//如果l到y是一块，也要乘
ans=ans*s[t]%Mod;
}
int main(){
// freopen("ranking.in","r",stdin);
// freopen("ranking.out","w",stdout);
read();
sort(a+1,a+n+1,cmp);//排序
printf("%lld",dfs(1,n,0)); //分治
}