POJ 3886 - Baby's Blocks

http://poj.org/problem?id=3886

概要

長さ \(L\) の文字列 \(s\) が与えられるので、 \(s\) を並び換えて得られる文字列のうち \(s\) は辞書順で何番目かを答える。

制約

解法

\(i\) 番目の文字が \(s[i]\) になるには、それより前に何種類の文字列があるのか組合せを計算しつつ足していくだけ。

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   long long fact[21];
 9   fact[0] = 1;
10   for (int i = 1; i <= 20; i++) {
11     fact[i] = i * fact[i-1];
12   }
13 
14   ios::sync_with_stdio(false);
15   int T;
16   cin >> T;
17   while (T-- > 0) {
18     string s;
19     while (cin >> s) {
20       long long ans = 0;
21       const int N = s.size();
22       for (int i = 0; i < N; i++) {
23         vector<int> v(26, 0);
24         for (int j = i; j < N; j++) {
25           ++v[s[j]-'A'];
26         }
27         for (char c = 'A'; c < s[i]; c++) {
28           long long a = fact[N-i-1];
29           --v[c-'A'];
30           for (int j = 0; j < 26; j++) {
31             a /= fact[v[j]];
32           }
33           ++v[c-'A'];
34           ans += a;
35         }
36       }
37       cout << ans << endl;
38     }
39   }
40   return 0;
41 }
poj/3886.cc