桁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; }