P7758 [COCI2012-2013#3] HERKABE 题解

· · 题解

题面传送门

首先，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