CF895 - String Mark（组合数学）

题目链接：

题目链接

题目大意：

给出两个字符串 A 和 B，问将第一个字符串的所有排列中，大于字典序大于 A 并且 小于 B 的排列有多少个。

字符串只包含小写字母，长度小于 $10^6$ 。

题目分析：

首先将问题简化，我们定义函数 $F(S, D)$ 为 S 字典序小于 D 的排列的数量，那么答案就是 $F(S, S) - F(S, D) - 1$

那么问题转化为求解这个函数，我们这里去枚举小于 D 的排列的前缀。

假设 D 为 “bcd”，如果前缀长度为 1，那么保证前缀为 “a”，剩下的进行任意排列即可；

如果前缀长度为 2，那么保证前缀为 “ba”，”bb” 对剩下的进行任意排列即可。

注意这里对于长度为 i 的前缀，它们和 D 拥有长度为 i - 1 的公共前缀。

不难想到这样就可以计算出所有字典序小于 D 的排列。

注意这里要用到多重集的排列公式：$\frac{n!}{n_1!n_2!\cdots n_k!}$

AC代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int MAX = 1123456;

string str1, str2;

ll pow_mod(ll a, ll k) {
    ll rst = 1;
    while (k) {
        if (k & 1) rst = rst * a % MOD;
        a = a * a % MOD;
        k >>= 1;
    }
    return rst;
}

ll rev[MAX], fac[MAX];
void init() {
    //初始化逆元
    for (int i = 1; i < MAX; i++) {
        rev[i] = pow_mod(i, MOD - 2);
    }
    fac[1] = 1;
    //初始化阶乘
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
    }
}

//求阶乘的逆元
ll rev_fac(ll n) {
    ll rst = 1;
    for (int i = 1; i <= n; i++) {
        rst = rst * rev[i] % MOD;
    }
    return rst;
}

ll cnt[MAX];

ll solve(string &str, string &cmp) {
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < str.size(); i++) {
        cnt[str[i] - 'a']++;
    }

    ll rst = 0, now = fac[str.size()];
    for (int i = 0; i < 26; i++) {
        if (!cnt[i]) continue;
        now = now * rev_fac(cnt[i]) % MOD;
    }

    for (int i = 0; i < str.size(); i++) {
        //now用来维护去掉当前某个字母后剩下的排列数量
        now = now * rev[str.size() - i] % MOD;
        for (int j = 0; j < cmp[i] - 'a'; j++) {
            if (!cnt[j]) continue;
            rst = (rst + now * cnt[j] % MOD) % MOD;
        }
        if (cnt[cmp[i] - 'a'] == 0) break;
        else {
            now = now * cnt[cmp[i] - 'a'] % MOD;
            cnt[cmp[i] - 'a']--;
        }
    }
    return rst;
}

int main() {
    init();
    cin >> str1 >> str2;
    ll rst1 = solve(str1, str1);
    ll rst2 = solve(str1, str2);
    printf("%lld\n", (rst2 - rst1 - 1 + MOD) % MOD);
}

解题过程：

完全没想到用排列计算，反而去想怎么构造了emmm