fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <vector>
  4. #include <boost/multiprecision/cpp_int.hpp>
  5.  
  6. using namespace std;
  7. using BigInt = boost::multiprecision::cpp_int;
  8.  
  9. BigInt ithDuplicatedPermutationInv(vector<int> a)
  10. {
  11.     int N = a.size();
  12.     BigInt i = 1, P = 1;
  13.     map<int, int> c;
  14.  
  15.     for (int j = N - 1; j >= 0; j--) {
  16.         c[a[j]]++;
  17.         int s = 0;
  18.         for (auto &x : c) {
  19.             if (x.first == a[j]) {
  20.                 i += P * s / x.second;
  21.                 P = P * (N - j) / x.second;
  22.                 break;
  23.             }
  24.             s += x.second;
  25.         }
  26.     }
  27.  
  28.     return i;
  29. }
  30.  
  31. template <typename T> ostream &operator<<(ostream &os, const vector<T> &v)
  32. {
  33.     for (auto &x : v) os << (&x == &v[0] ? "[" : ", ") << x;
  34.     cout << "]";
  35.     return os;
  36. }
  37.  
  38. const vector<int> nothing = {};
  39.  
  40. vector<int> Q[] = {
  41.     {1, 2, 3, 4, 5, 6, 7, 8, 9},
  42.     {1, 2, 3, 4, 5, 6, 7, 9, 8},
  43.     {1, 2, 3, 4, 5, 6, 8, 7, 9},
  44.     {9, 8, 7, 6, 5, 4, 3, 2, 1},
  45.     nothing,
  46.     {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4},
  47.     {1, 1, 1, 2, 2, 2, 3, 3, 4, 3, 4, 4},
  48.     {1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 3, 4},
  49.     {2, 2, 2, 3, 3, 1, 4, 3, 4, 1, 1, 4},
  50.     {3, 2, 4, 4, 2, 4, 3, 3, 1, 1, 1, 2},
  51.     {4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1},
  52.     nothing,
  53.     {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5},
  54.     {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 4, 5, 5},
  55.     {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 4, 5},
  56.     {1, 1, 1, 3, 3, 3, 4, 4, 2, 5, 4, 5, 2, 2, 5},
  57.     {1, 1, 1, 4, 3, 5, 5, 3, 5, 4, 4, 2, 2, 2, 3},
  58.     {1, 1, 1, 5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2},
  59.     {5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1},
  60.     nothing,
  61.     {1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 
  62.      6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10},
  63.     {1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
  64.      6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 9, 10, 10, 10, 10},
  65.     {1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
  66.      6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 9, 10, 10, 10},
  67.     {1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
  68.      6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10, 8, 8, 9, 8, 8, 9, 10, 10, 10, 9},
  69.     {1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
  70.      6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 10, 10, 9, 8, 8, 9, 10, 10, 8, 9, 10, 9, 8, 9},
  71.     {10, 10, 10, 10, 10, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6,
  72.      5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1},
  73.     nothing,
  74.     {3, 1, 4, 1, 5, 9}
  75. };
  76.  
  77. int main(void)
  78. {
  79.     for (auto &q : Q) {
  80.         if (q.size()) {
  81.             cout << "入力: " << q << endl;
  82.             cout << "出力: " << ithDuplicatedPermutationInv(q) << endl;
  83.         }
  84.         cout << endl;
  85.     }
  86.  
  87.     return 0;
  88. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
入力: [1, 2, 3, 4, 5, 6, 7, 8, 9]
出力: 1

入力: [1, 2, 3, 4, 5, 6, 7, 9, 8]
出力: 2

入力: [1, 2, 3, 4, 5, 6, 8, 7, 9]
出力: 3

入力: [9, 8, 7, 6, 5, 4, 3, 2, 1]
出力: 362880


入力: [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4]
出力: 1

入力: [1, 1, 1, 2, 2, 2, 3, 3, 4, 3, 4, 4]
出力: 2

入力: [1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 3, 4]
出力: 3

入力: [2, 2, 2, 3, 3, 1, 4, 3, 4, 1, 1, 4]
出力: 123456

入力: [3, 2, 4, 4, 2, 4, 3, 3, 1, 1, 1, 2]
出力: 234567

入力: [4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1]
出力: 369600


入力: [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5]
出力: 1

入力: [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 4, 5, 5]
出力: 2

入力: [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 4, 5]
出力: 3

入力: [1, 1, 1, 3, 3, 3, 4, 4, 2, 5, 4, 5, 2, 2, 5]
出力: 123456

入力: [1, 1, 1, 4, 3, 5, 5, 3, 5, 4, 4, 2, 2, 2, 3]
出力: 234567

入力: [1, 1, 1, 5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2]
出力: 369600

入力: [5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1]
出力: 168168000


入力: [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10]
出力: 1

入力: [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 9, 10, 10, 10, 10]
出力: 2

入力: [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 9, 10, 10, 10]
出力: 3

入力: [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10, 8, 8, 9, 8, 8, 9, 10, 10, 10, 9]
出力: 123456

入力: [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 10, 10, 9, 8, 8, 9, 10, 10, 8, 9, 10, 9, 8, 9]
出力: 234567

入力: [10, 10, 10, 10, 10, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1]
出力: 49120458506088132224064306071170476903628800


入力: [3, 1, 4, 1, 5, 9]
出力: 127
https://ideone.com/Lne3AQ
language:
C++14 (gcc 8.3)
created:
27 days ago
visibility:
secret

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!