CF #588 D. Wojtek and Card Tricks

https://codeforces.com/contest/1229/problem/D

Consider this problem : How many permutations can be represented by the product of P[L] ... P[R]? In other words, please find the order of the group generated by P[L] ... P[R]. Then, this answer must be the divisor of K!. the number of the divisors of 120 is 16, it is small. So we try using this fact for solving this task.

Fix the right-end of the interval. Then, considering the sequence of f(R,R), f(R-1,R), f(R-2,R)..., we notice that this sequence changes at most 16 times. Moreover, for all interval a b such that f(a)=f(b), the group generated by a and by b are the exactly same. Therefore, we can solve this problem by maintaining the number of intervals taking the same value and unionfinds. We can update R to R+1 efficiently, so the time complexity becomes O(N * 16 * 120 * UF). Actually, 16 is over estimation, the actual bound is 6.

Source Code

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()

using namespace std;
using ll = long long;
using ull = unsigned long long;

struct unionfind {
  vector<int> dat;

  unionfind(int n) : dat(n, -1) {}

  int find(int x) {
    if (dat[x] < 0) return x;
    return dat[x] = find(dat[x]);
  }

  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (dat[x] > dat[y]) swap(x, y);
    dat[x] += dat[y];
    dat[y] = x;
  }

  int size(int x) {
    return -dat[find(x)];
  }
};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N, K; cin >> N >> K;
  vector<vector<int>> A(N, vector<int>(K));
  rep(i, N) {
    rep(j, K) cin >> A[i][j], A[i][j]--;
  }
  map<vector<int>, int> f;
  vector<vector<int>> g;
  vector<int> perm(K);
  rep(i, K) perm[i] = i;
  do {
    f[perm] = g.size();
    g.push_back(perm);
  } while (next_permutation(range(perm)));
  const int F = g.size();
  auto mult = [&](vector<int> a, vector<int> b) {
    vector<int> c(K);
    rep(i, K) c[i] = a[b[i]];
    return c;
  };
  vector<vector<int>> table(F, vector<int>(F));
  rep(i, F) rep(j, F) {
    table[i][j] = f[mult(g[i], g[j])];
  }
  vector<int> divs;
  for (int i = 1; i <= F; i++) {
    if (F % i == 0) {
      divs.push_back(i);
    }
  }
  vector<unionfind> uf(divs.size(), unionfind(F));
  vector<ll> dp(divs.size());
  dp[0]++;
  ll ans = 0;
  rep(i, N) {
    int p = f[A[i]];
    repr(j, divs.size()) if (dp[j] != 0) {
      rep(k, F) uf[j].unite(k, table[p][k]);
      if (uf[j].size(0) != divs[j]) {
        int k = find(range(divs), uf[j].size(0)) - divs.begin();
        assert(j < k && k < divs.size());
        uf[k] = uf[j];
        dp[k] += dp[j];
        dp[j] = 0;
      }
    }
    rep(j, divs.size()) ans += dp[j] * divs[j];
    dp[0]++;
    uf[0] = unionfind(F);
  }
  cout << ans << endl;
}