今天去翻 div2 的题，发现 E 竟然一年前做过？看到题就有印象了，不过解读自己代码读了半天。
所以这是我一年前做出来的题，没场切的好好反思。
分字符串的每一位来讨论。假设当前讨论到第 位，前面 位就划分出了若干个 lcp 相同的等价类。我们此时考虑交换两个字符串位置，则只能在同一个等价类中交换。这是第一个限制。
考虑还有什么限制，考虑第 位的限制。加上第 位后，一个等价类可能变成多个，带来的限制同样是不能跨越这几个等价类交换。
综合上面的条件，发现我们如果想改变若干个字符串的位置，则只能把加上第 位后的若干个等价类视作一个元素，在原来的等价类里任意排列，方案数即为阶乘。
所以发现，只要从前往后枚举 ，找到这些等价类然后将方案数相乘即可。为了方便找到，可以先排序。具体实现就是记录每个等价类的左右端点处理。时间复杂度是优秀的 。
确实是一道组合数学好题。oplq 学长有一种递归的优美写法，这里放我的不递归写法代码供参考：
int n,m,sum,mxn,ans=1,cnt[30],l[maxn],r[maxn],nl[maxn],nr[maxn],f[maxn];
string str[maxn];
signed main(){
scanf("%lld",&n);
f[0]=1;
getchar();
for(int i=1;i<=n;i++)cin>>str[i],mxn=max(mxn,(int)str[i].size()),f[i]=f[i-1]*i%mod;
sort(str+1,str+n+1);
sum=1;
l[1]=1;r[1]=n;
for(int k=0;k<=3000;k++){
int tot=0;
memset(nl,0,sizeof nl);
memset(nr,0,sizeof nr);
for(int i=1;i<=sum;i++){
int now=0;
memset(cnt,0,sizeof cnt);
nl[++tot]=l[i];
for(int j=l[i];j<=r[i];j++){
if(str[j].size()>=k+1)cnt[str[j][k]-'A'+1]++;
else cnt[0]++;
if(j!=l[i]&&(str[j].size()<=k+1||str[j][k]!=str[j-1][k]))nr[tot]=j-1,nl[++tot]=j;
}
nr[tot]=r[i];
for(int i=0;i<=26;i++){
if(cnt[i])now++;
}
ans=ans*f[now]%mod;
}
for(int i=1;i<=tot;i++)l[i]=nl[i],r[i]=nr[i];
sum=tot;
}
printf("%lld",ans);
}
