cf1649 E. Tyler and Strings

题意：

给定长为 n 的序列 a 和长为 m 的序列 b，问将 s 重新排列后能得到多少个不同的字典序小于 b 的序列。

两个序列 a,b 被视为不同当且仅当至少存在一个 i 使得 \(a_i\neq b_i\)。

思路：

从左到右，要么选比 \(b_i\) 小的，要么选 \(a_i=b_i\) 并继续

注意这是个多重集排列数，

如果拿掉某个数 \(a_i\)，就会乘上 \(\frac{cnt_{a_i}}{n}\)

开个树状数组

具体还挺麻烦的。还要注意处理长度不一致的情况

ll n, m, a[N], b[N], cnt[N];

ll jc[N], jcni[N], ni[N];
void init(int n = N-1) {
    jc[0] = 1;
    for(int i = 1; i <= n; i++) jc[i] = jc[i-1] * i % mod;
    jcni[n] = qmi(jc[n], mod-2);
    for(int i = n; i; i--) jcni[i-1] = jcni[i] * i % mod;
    ni[1] = 1;
    for(int i = 2; i <= n; i++) ni[i] = (mod-mod/i) * ni[mod%i] % mod;
}

signed main() {
    iofast;
    init();
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i], add(a[i], 1), cnt[a[i]]++;
    for(int i = 1; i <= m; i++) cin >> b[i];

    ll ans = 0, res = jc[n];
    for(int i = 1; i < N; i++)
        (res *= jcni[cnt[i]]) %= mod;

    for(int i = 1; i <= n; i++) {
        (ans += res * ni[n+1-i] % mod * ask(b[i]-1) % mod) %= mod;
        (res *= cnt[b[i]] * ni[n+1-i] % mod) %= mod;
        if(cnt[b[i]]) cnt[b[i]]--, add(b[i], -1);
        else break;
        if(i == n && n < m) (ans += 1) %= mod;
    }

    cout << ans;
}