fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <string>
  4. using namespace std;
  5.  
  6. // Function to calculate factorial
  7. long long fact(int f) {
  8.     if (f == 0 || f == 1) return 1;
  9.     return f * fact(f - 1);
  10. }
  11.  
  12. // Function to calculate rank of a string
  13. void solve(string s, int n) {
  14.     long long ans = 1;
  15.     map<char, int> freq;
  16.     int len = n - 1;
  17.  
  18.     // Count character frequencies
  19.     for (int i = 0; i < n; i++) {
  20.         freq[s[i]]++;
  21.     }
  22.  
  23.     // Calculate rank
  24.     for (int i = 0; i < n; i++) {
  25.         char c = s[i];
  26.  
  27.         // Calculate permutations for characters smaller than current
  28.         for (auto& pair : freq) {
  29.             if (pair.first >= c) break;
  30.             if (pair.second > 0) {
  31.                 pair.second--;
  32.                 long long denominator = 1;
  33.                 for (auto& f : freq) {
  34.                     denominator *= fact(f.second);
  35.                 }
  36.                 ans += (fact(len) / denominator);
  37.                 pair.second++;
  38.             }
  39.         }
  40.  
  41.         freq[c]--;
  42.         if (freq[c] == 0) {
  43.             freq.erase(c);
  44.         }
  45.         len--;
  46.     }
  47.  
  48.     cout << ans << endl;
  49. }
  50.  
  51. int main() {
  52.     string s;
  53.     cin >> s;
  54.     solve(s, s.size());
  55.     return 0;
  56. }
  57.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
MISSISSIPPI
stdout
copy 
13737
https://ideone.com/6bzMpX
language:
C++ (gcc 8.3)
created:
25 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!