Prefix Free Code（字符串）

## Prefix Free Code

题意

给你n个字符串，这些字符串都不是互相的前缀，再给你一个模式串。模式串由k个其中的字符串任意排列组成。求这个模式串是从中选k个按照字典序排列组成的第几个串？

思路

用全排列的方法，1~n表示前n个字符串，用字符串哈希的方法把他们压缩成数字放在map里映射字符串的序号。

然后遍历模式串。对于每找到一个字符串，按照（比此序号小的字符串-前面已经用掉的字符串的个数）*剩下的位子的全排列数量乘以原先算出来的种数，然后把这个新找到的字符串add到树状数组中，用来标记已经用掉的字符串的个数。

看！代码

#include <bits/stdc++.h>
#define MOD 1000000007
#define MAXN 1000010
using namespace std;
typedef long long ll;
ll fac[1000010];
ll inv[1000010];
string s[1000010];
string ss;
const ll base=131;
const ll mod=1234567891011ll;
unordered_map<ll,int>mp;
ll solve(int id)
{
    int len=s[id].size();
    ll ans=0;
    for(int i=0;i<len;i++)
        ans=(ans*base+(s[id][i]))%mod;
    return ans;//
}
int n;
int d[1000010];
int lowbit(int x)
{
    return x&(-x);
}
int query(int x)
{
    int res=0;
    while(x)
    {
        res+=d[x];
        x-=lowbit(x);
    }
    return res;
}
void add(int x,int v)
{
    while(x<=n)
    {
        d[x]+=v;
        x+=lowbit(x);
    }
}
ll PowerMod(ll a,ll b,ll c)
{
    ll ans=1;
    ll k;
    k=a;
    k=k%c;
    while(b>0)
    {
        if(b&1)
            ans=(ans*k)%c;
        b>>=1;
        k=(k*k)%c;
    }
    return ans;
}
void init()
{
    fac[0]=fac[1]=1;
    for(int i=2;i<=MAXN;i++)
        fac[i]=fac[i-1]*i%MOD;
    inv[MAXN]=PowerMod(fac[MAXN],MOD-2,MOD);
    for(int i=MAXN-1;i>=0;i--)
        inv[i]=inv[i+1]*(i+1)%MOD;
}
int main()
{
    init();
    int k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        cin>>s[i];
    sort(s+1,s+n+1);
    for(int i=1;i<=n;i++)
    {
        ll tot=solve(i);
        mp[tot]=i;
    }
    cin>>ss;
    int len=ss.size();
    ll temp=0;
    ll ans=0;
    int cnt=0;
    for(int i=0;i<len;i++)
    {
        temp=(temp*base+(ss[i]))%mod;
        if(mp[temp]!=0)
        {
            cnt++;
            int id=mp[temp];
            ll sum=1;
            sum=id-1-query(id);
            sum=((fac[n-cnt]*inv[n-k])%MOD*sum)%MOD;
            ans=(ans+sum)%MOD;
            temp=0;
            add(id,1);
        }
    }
    printf("%lld\n",(ans+1)%MOD);
    return 0;
}