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 factorial(unsigned int n)
  10. {
  11.     for (BigInt f = 1; ; f *= n--) if (!n) return f;
  12. }
  13.  
  14. BigInt ithDuplicatedPermutationInv(vector<int> a)
  15. {
  16.     int N = a.size();
  17.     BigInt i = 1;
  18.  
  19.     map<int, int> c;
  20.     for (int x : a) c[x]++;
  21.  
  22.     BigInt P = factorial(N);
  23.     for (auto &x : c) P /= factorial(x.second);
  24.  
  25.     for (int j = 0; j < N; j++) {
  26.         int s = 0;
  27.         for (auto &x : c) {
  28.             if (x.first == a[j]) {
  29.                 i += P * s / (N - j);
  30.                 P = P * x.second / (N - j);
  31.                 x.second--;
  32.                 break;
  33.             }
  34.             s += x.second;
  35.         }
  36.     }
  37.  
  38.     return i;
  39. }
  40.  
  41. template <typename T> ostream &operator<<(ostream &os, const vector<T> &v)
  42. {
  43.     for (auto &x : v) os << (&x == &v[0] ? "[" : ", ") << x;
  44.     cout << "]";
  45.     return os;
  46. }
  47.  
  48. const vector<int> nothing = {};
  49.  
  50. vector<int> Q[] = {
  51.     {1, 2, 3, 4, 5, 6, 7, 8, 9},
  52.     {1, 2, 3, 4, 5, 6, 7, 9, 8},
  53.     {1, 2, 3, 4, 5, 6, 8, 7, 9},
  54.     {9, 8, 7, 6, 5, 4, 3, 2, 1},
  55.     nothing,
  56.     {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4},
  57.     {1, 1, 1, 2, 2, 2, 3, 3, 4, 3, 4, 4},
  58.     {1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 3, 4},
  59.     {2, 2, 2, 3, 3, 1, 4, 3, 4, 1, 1, 4},
  60.     {3, 2, 4, 4, 2, 4, 3, 3, 1, 1, 1, 2},
  61.     {4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1},
  62.     nothing,
  63.     {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5},
  64.     {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 4, 5, 5},
  65.     {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 4, 5},
  66.     {1, 1, 1, 3, 3, 3, 4, 4, 2, 5, 4, 5, 2, 2, 5},
  67.     {1, 1, 1, 4, 3, 5, 5, 3, 5, 4, 4, 2, 2, 2, 3},
  68.     {1, 1, 1, 5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2},
  69.     {5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1},
  70.     nothing,
  71.     {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, 
  72.      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},
  73.     {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,
  74.      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},
  75.     {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,
  76.      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},
  77.     {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,
  78.      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},
  79.     {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,
  80.      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},
  81.     {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,
  82.      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},
  83.     nothing,
  84.     {3, 1, 4, 1, 5, 9}
  85. };
  86.  
  87. int main(void)
  88. {
  89.     for (auto &q : Q) {
  90.         if (q.size()) {
  91.             cout << "入力: " << q << endl;
  92.             cout << "出力: " << ithDuplicatedPermutationInv(q) << endl;
  93.         }
  94.         cout << endl;
  95.     }
  96.  
  97.     return 0;
  98. }
Success #stdin #stdout 0s 5320KB
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/dmETd5
language:
C++14 (gcc 8.3)
created:
30 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!