fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. constexpr int MOD = 1000000007;
  4. constexpr int N = 1000000;
  5. constexpr int K = 8;
  6. int invmod[100]; // modular inverses for binomial computation
  7.  
  8. // compute binomial coefficient
  9. int choose(int n, int m) {
  10.   int res = 1;
  11.   for (int i = 1; i <= m; ++i)
  12.     res = (int64_t) res * (n - i + 1) % MOD * invmod[i] % MOD;
  13.   return res;
  14. }
  15.  
  16. int LIS(std::vector<int> ordering) {
  17.   int n = ordering.size();
  18.   std::vector<int> f(n, 1);
  19.   for (int i = 1; i < n; ++i)
  20.     for (int j = 0; j < i; ++j)
  21.       if (ordering[j] < ordering[i])
  22.         f[i] = std::max(f[i], f[j] + 1);
  23.   return *std::max_element(f.begin(), f.end());
  24. }
  25.  
  26. std::vector<int> check_strict_ordering() {
  27.   std::vector<int> p(K);
  28.   iota(p.begin(), p.end(), 0);
  29.   std::vector<int> counts(K + 1, 0);
  30.   do {
  31.     int L = LIS(p);
  32.     int descents = 0;
  33.     for (int i = 1; i < K; ++i)
  34.       descents += p[i] < p[i - 1];
  35.     counts[L] = (counts[L] + choose(N + descents, K)) % MOD;
  36.   } while (std::next_permutation(p.begin(), p.end()));
  37.   return counts;
  38. }
  39.  
  40.  
  41. std::vector<int> check_weak_ordering() {
  42.   std::vector<int> counts(K + 1, 0);
  43.  
  44.   auto process = [&](std::vector<int> ordering) {
  45.     int unique_count = std::set<int>(ordering.begin(), ordering.end()).size();
  46.     do {
  47.       int L = LIS(ordering);
  48.       counts[L] = (counts[L] + choose(N, unique_count)) % MOD;
  49.     } while (std::next_permutation(ordering.begin(), ordering.end()));
  50.   };
  51.  
  52.   std::vector<int> ordering;
  53.   std::function<void(int, int)> generate = [&](int pos, int left) {
  54.     if (pos >= K) {
  55.       if (left == 0) {
  56.         process(ordering);
  57.       }
  58.       return;
  59.     }
  60.     for (int take = 1; take <= left; ++take) {
  61.       ordering.push_back(pos);
  62.       generate(pos + 1, left - take);
  63.     }
  64.     if (left == 0)
  65.       generate(pos + 1, left);
  66.     while (!ordering.empty() && ordering.back() == pos)
  67.       ordering.pop_back();
  68.   };
  69.  
  70.   generate(0, K);
  71.  
  72.   return counts;
  73. }
  74.  
  75. int main() {
  76.   invmod[1] = 1;
  77.   for (int i = 2; i < 100; ++i) {
  78.     invmod[i] = (MOD - (int64_t) (MOD / i) * invmod[MOD % i] % MOD) % MOD;
  79.     assert((int64_t) invmod[i] * i % MOD == 1);
  80.   }
  81.  
  82.   std::vector<int> c1 = check_strict_ordering();
  83.   std::vector<int> c2 = check_weak_ordering();
  84.  
  85.   for (int i = 1; i <= K; ++i) {
  86.     std::cout << c1[i] << ' ' << c2[i] << '\n';
  87.     assert(c1[i] == c2[i]);
  88.   }
  89.   return 0;
  90. }
Success #stdin #stdout 0.09s 4476KB
comments (?)
stdin 
Standard input is empty
stdout 
456179811 456179811
826112001 826112001
362449087 362449087
662512874 662512874
850248061 850248061
632592721 632592721
958525633 958525633
234572847 234572847
https://ideone.com/mDo1pG
language:
C++14 (gcc 8.3)
created:
4 years 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!