Zerojudge i821：一番賞問題

Zerojudge i821：一番賞問題

題目大意：給一個字串，裡面可能有 $a\sim t$ 的字元，每次抽一個，問 $a$ 比其它字母先抽完的方法數（字母相同視為相同）。

解法：可以用排容，用 $2^{\text{sz}-1}$ 枚舉除了 $a$ 以外的字母哪些要放在最後一個 $a$ 前面，哪些要隨便放，令 $\text{sum}=\text{cnt}_{a}+\sum\limits_{x\in\text{mask}}\text{cnt}_x$，那 $\text{mask}$ 裡的字母都放在最後一個 $a$ 前面的方法數有 $\frac{(\text{sum}-1)!}{(\text{cnt}_a-1)!\prod\limits_{x\in\text{mask}}\text{cnt}_x!}$，隨便放的方法數有 $\frac{(n-\text{sum})!}{\prod\limits_{x\notin\text{mask}}\text{cnt}_x!}$，總方法數就是兩個相乘再乘以 $\frac{n!}{\text{sum}!(n-\text{sum})!}$。

答案會是 $\sum\limits_{\text{mask}}(-1)^{|\text{mask}|}\frac{n!}{\text{sum}(\text{cnt}_a-1)!\prod\limits_x \text{cnt}_x!}$，直接算的複雜度是 $O(n2^n)$，注意到這個式子可以 $O(1)$ 維護，所以其實可以做到 $O(2^n)$。

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout (T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int MOD = 1e9 + 7;
const int N = 1e6 + 5;

int n, ans;
string s;
int sz, cnt[26];
int pro[N], inv[N];

int power(int d, int up) {
    int re = 1;
    while (up) {
        if (up & 1) re = 1ll * re * d % MOD;
        d = 1ll * d * d % MOD;
        up >>= 1;
    }
    return re;
}

void solve() {
    cin >> s;
    n = s.size();
    for (char c : s) cnt[c - 'a']++;
    FOR (i, 0, 25) if (cnt[i]) cnt[sz++] = cnt[i];
    pro[0] = 1;
    FOR (i, 1, n) pro[i] = 1ll * pro[i - 1] * i % MOD;
    inv[n] = power(pro[n], MOD - 2);
    for (int i = n; i >= 1; i--) inv[i - 1] = 1ll * inv[i] * i % MOD;
    sz--;
    int num = inv[cnt[0] - 1];
    FOR (i, 1, sz) num = 1ll * num * inv[cnt[i]] % MOD;
    FOR (mask, 0, (1 << sz) - 1) {
        int c = 0, sum = cnt[0], val = num;
        FOR (i, 1, sz) if (mask >> (i - 1) & 1) {
            c++;
            sum += cnt[i];
        }
        val = 1ll * val * pro[sum - 1] % MOD * pro[n] % MOD * inv[sum] % MOD;
        if (c & 1) ans += MOD - val;
        else ans += val;
        if (ans >= MOD) ans -= MOD;
    }
    cout << ans << '\n';
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！