JOI 春合宿 2007 day3-1 anagram (難易度 6)

桁DPとは違うけど、桁DP的な発想で解けた

• ジャッジページへのリンク

問題概要

長さ の文字列 が与えられる。

の各文字を並び替えてできる文字列をすべて考えたとき、 はその中で辞書順で何番目の文字列に相当するのかを求めよ。

制約

• 
• の文字はすべて英大文字

考えたこと

よりも辞書順で小さい文字列の個数を数え上げて、最後に 1 を足せば OK。

よりも辞書順の小さい文字列は、以下のように捉えることができる。

---

• 最初の 文字は と一致する
• 文字目が よりも小さい (0-indexed)
• それ以降は自由に並び替えて良い

---

について場合分けして、丁寧に数え上げよう。なお、たとえば

• 'A' が 文字
• 'B' が 文字
• 'C' が 文字

であるような文字列を並び替えてできる文字列の個数は

個

となる。ここでは 3 種類の文字のみを考えたが、26 種類になっても同様にできる。 が小さいので、あらかじめ を前処理で求めておくと楽。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S; cin >> S;
    int N = S.size();
    vector<long long> fac(N+1, 1);
    for (int n = 1; n <= N; ++n) fac[n] = fac[n-1] * n;

    auto com = [&](int sum, const vector<int> &num) -> long long {
        long long res = fac[sum];
        for (int i = 0; i < 26; ++i) res /= fac[num[i]];
        return res;
    };

    vector<int> num(26, 0);
    for (int i = 0; i < N; ++i) num[S[i]-'A']++;
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        for (int c = 0; c < S[i]-'A'; ++c) {
            if (!num[c]) continue;
            num[c]--;
            res += com(N-i-1, num);
            num[c]++;
        }
        num[S[i]-'A']--;
    }
    cout << res+1 << endl;
}