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;
}

AGC 038 C - LCMs

https://atcoder.jp/contests/agc038/tasks/agc038_c

Before solving this task, solve this problem.

\begin{align}
f_k = \sum_{\mathrm{gcd}(i, j)=k} a_i b_j.
\end{align}

We can find this from the following by inclusion-exclusion principle.

\begin{align}
F_k = \sum_{k \mid i \land k \mid j} a_i b_j.
\end{align}

That is, the common divisor is easier than the greatest common divisor. First, this holds.

\begin{align}
F_k = f_k + f_{2k} + f_{3k} + f_{4k} + \cdots
\end{align}

$F_k$ can be decomposed into two factors.

\begin{align}
F_k = \sum_{k \mid i \land k \mid j} a_i b_j = \left(\sum_{k \mid i} a_i\right) \left(\sum_{k \mid j} b_j\right).
\end{align}

We now have $F_1, F_2, F_3, \ldots$. Last, we reduce them into $f_1, f_2, f_3, \ldots$ by inclusion-exclusion. The formula is this.

\begin{align}
f[k] = F[k] - F[2k] - F[3k] - F[5k] + F[6k] + F[10k] + F[15k] - \cdots
\end{align}

Precisely,

\begin{align}
f[k] = F[k] - \sum_{p} F[pk] + \sum_{p \lt q} F[pqk] - \sum_{p \lt q \lt r} F[pqrk] + \cdots.
\end{align}

If we use moebius function, we obtain another expression.

\begin{align}
f[k] = \sum_{k \mid i} \mu\left( \frac{i}{k} \right)F[i].
\end{align}

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;

constexpr int MOD = 998244353;

class mint {
  int n;
public:
  mint(int n_ = 0) : n(n_) {}
  explicit operator int() { return n; }
  friend mint operator-(mint a) { return -a.n + MOD * (a.n != 0); }
  friend mint operator+(mint a, mint b) { int x = a.n + b.n; return x - (x >= MOD) * MOD; }
  friend mint operator-(mint a, mint b) { int x = a.n - b.n; return x + (x < 0) * MOD; }
  friend mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
  friend mint &operator+=(mint &a, mint b) { return a = a + b; }
  friend mint &operator-=(mint &a, mint b) { return a = a - b; }
  friend mint &operator*=(mint &a, mint b) { return a = a * b; }
  friend bool operator==(mint a, mint b) { return a.n == b.n; }
  friend bool operator!=(mint a, mint b) { return a.n != b.n; }
  friend istream &operator>>(istream &i, mint &a) { return i >> a.n; }
  friend ostream &operator<<(ostream &o, mint a) { return o << a.n; }
};
mint operator "" _m(unsigned long long n) { return n; }

// c[gcd(i, j)] += a[i] * b[j]
vector<mint> zeta(vector<mint> f) {
  const int n = f.size();
  for (int i = 1; i < n; i++) {
    for (int j = i * 2; j < n; j += i) {
      f[i] += f[j];
    }
  }
  return f;
}

vector<mint> moebius(vector<mint> f) {
  const int n = f.size();
  for (int i = n - 1; i >= 1; i--) {
    for (int j = i * 2; j < n; j += i) {
      f[i] -= f[j];
    }
  }
  return f;
}


int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  constexpr int U = 1e6;
  vector<mint> inv(U + 1);
  inv[1] = 1;
  for (int i = 2; i <= U; i++) {
    inv[i] = inv[MOD % i] * (MOD - MOD / i);
  }
  int N; cin >> N;
  vector<mint> f(U + 1);
  vector<int> A(N);
  rep(i, N) {
    cin >> A[i];
    f[A[i]] += A[i];
  }
  f = zeta(f);
  for (int i = 1; i <= U; i++) {
    f[i] *= f[i];
  }
  f = moebius(f);
  mint ans = 0;
  for (int i = 1; i <= U; i++) {
    ans += f[i] * inv[i];
  }
  rep(i, N) {
    ans -= mint(A[i]);
  }
  ans *= inv[2];
  cout << ans << endl;
}

Educational Codeforces 73 E. Game With String

https://codeforces.com/contest/1221/standings

First, if there is a segment whose length x is B <= x < A, the second player always wins. That's why the number of possible movements of the second player is always larger than the first player if the second player moves optimally. This is a really important property, so it appears again and again.

Second, if there are two or more segments whose length x is 2B, the second player always wins. The optimal movement of the second player is to make segment of length B.

One of the simplest situation is all segments belong to the group [A,2*B) the winner is decided by the parity of the its number. Last, we consider the situation that the only single segment belongs to the group [2*B,inf) and the others belong to the group [A,2*B). Let c be the number of segments [A,2*B) and v denotes the length of the segment of [2*B,inf). If c is even, the first player should split v into [0,B) and [0,B) or [A,2*B) and [A,2*B). In the both cases, we should divide the segment equally. Next, consider the case that c is odd. In this case, the first player should split v into [0,B) and [A,2*B). Let x be the length of the part of [0,B) and y be the length of the part of [A,2*B). The analysis of this case is a little difficult without algebra.

List the conditions x and y must follows.

\begin{gather}
x+y+A = v,\\
0 \le x < B, \\
A \le y < 2B
\end{gather}

We then have

\begin{gather}
0 \le x \lt B, \\
- 2B + v - A \lt x \le - 2 A + v.
\end{gather}

We now have all pieces to solve this problem. All we have to do is to implement conditions described above.

#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;
 
bool overlap(int a, int b, int c, int d) {
  return max(a, c) <= min(b, d);
}
 
bool solve() {
  int A, B; cin >> A >> B;
  string S; cin >> S;
  const int N = S.size();
  vector<int> val;
  for (int i = 0; i < N;) {
    if (S[i] == 'X') {
      i++;
      continue;
    }
    int j = i;
    while (i < N && S[i] == '.') i++;
    if (i - j >= B) {
      if (i - j < A) return false;
      val.push_back(i - j);
    }
  }
  int cnt = 0;
  for (int x : val) cnt += x >= 2 * B;
  if (cnt >= 2) return false;
  int v = 0;
  for (int x : val) if (x >= 2 * B) v = x;
  int l = (v - A) / 2;
  int r = (v - A + 1) / 2;
  if (r < B && val.size() % 2 == 1) return true;
  if (A <= l && l < 2*B && A <= r && r < 2*B && val.size() % 2 == 1) return true;
  if (val.size() % 2 == 0 & overlap(0, B-1, -A-2*B+1+v, -2*A+v)) return true;
  return false;
}
 
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int Q; cin >> Q;
  while (Q--) {
    cout << (solve() ? "YES" : "NO") << '\n';
  }
}

ABC141 E. Who Says a Pun?

https://atcoder.jp/contests/abc141/tasks/abc141_e

There exists the way to find LCS (longest common prefix) using DP. LCS, LCP and edit distance are typical problems of string DP. Since the ant book describes only LCS, LCS may be not well known.

#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;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N; cin >> N;
  string S; cin >> S;
  vector<vector<int>> lcp(N + 1, vector<int>(N + 1));
  int ans = 0;
  repr(i, N) {
    repr(j, N) {
      if (S[i] != S[j]) {
        lcp[i][j] = 0;
      } else {
        lcp[i][j] = lcp[i + 1][j + 1] + 1;
      }
      if (i < j) {
        ans = max(ans, min(j - i, lcp[i][j]));
      }
    }
  }
  cout << ans << endl;
}

We can find a lot of binary search solutions, but it is unnecessarily. We can solve this problem in O(N).

For example, if you have "bananaba", its suffix array is as follows.

Assume that the answer is greater or equal to 2. The pair of (i, j) must be included in the same group (see above figure.) Look at the group which contains "anana" and "ananaba". "anana" is a suffix at 3 and "ananaba" is a suffix at 1. Since abs(3-1)>=2, this assumption is correct, which concludes the answer is greater or equal to 2.

Assume that the answer is greater or equal to 3. In this case, the suffixes are decomposed into

If the answer is 3, only ("anana", "ananaba") is possible. However, this pair doesn't give the answer because abs(3-1)<3. Therefore, this assumption is incorrect, which concludes the answer is less than 3.

#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;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N; cin >> N;
  string S; cin >> S;
  // SA-IS O(n)
  vector<int> sa(N + 1); rep(i, N + 1) sa[i] = i;
  sort(range(sa), [&](int i, int j) {
    return S.substr(i) < S.substr(j);
  });
  // LCP O(n)
  vector<int> lcp(N + 1);
  rep(i, N) {
    int h = 0;
    while (sa[i] + h < N && sa[i + 1] + h < N && S[sa[i] + h] == S[sa[i + 1] + h]) h++;
    lcp[i] = h;
  }

  vector<int> ord(N);
  rep(i, N) ord[i] = i;
  // counting sort O(n)
  sort(range(ord), [&](int i, int j) { return lcp[i] > lcp[j]; });

  vector<int> l(N + 1);
  vector<int> r(N + 1);
  vector<int> mn(N + 1);
  vector<int> mx(N + 1);
  rep(i, N + 1) {
    l[i] = i;
    r[i] = i;
    mn[i] = sa[i];
    mx[i] = sa[i];
  }

  // O(n)
  int ans = 0;
  for (int i : ord) {
    int j = i + 1;
    int k = l[i];
    r[l[i]] = r[j];
    l[r[j]] = l[i];
    mn[k] = min(mn[k], mn[j]);
    mx[k] = max(mx[k], mx[j]);
    ans = max(ans, min(lcp[i], mx[k] - mn[k]));
  }
  cout << ans << endl;
}

figure: https://github.com/pekempey/figure/tree/master/ABC141E

ABC141 F Xor Sum 3

https://atcoder.jp/contests/abc141/tasks/abc141_f

If the number of ones on i-th bit is odd, 2^i is always added to the answer no matter how we classified them. Therefore, we can use an usual approach for finding lexicographically maximum. We can determine whether some bit can become one or not by using system of linear equations. We may solve this equation 60 times at worst, but which is fast enough.

If you are familiar with linear algebra, you can find more elegant solution, which written in the editorial. The following code is based on the editorial.

#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;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N; cin >> N;
  vector<ll> A(N); rep(i, N) cin >> A[i];
  ll ans = 0;
  rep(i, 60) {
    int s = 0;
    rep(j, N) s ^= A[j] >> i & 1;
    if (s == 1) {
      ans += 1LL << i;
      rep(j, N) A[j] &= ~(1LL << i);
    }
  }
  vector<ll> bases;
  sort(range(A), greater<>());
  for (ll x : A) {
    for (ll y : bases) x = min(x, x ^ y);
    if (x != 0) bases.push_back(x);
  }
  ll s = 0;
  for (ll x : bases) s = max(s, s ^ x);
  cout << ans + s * 2 << endl;
}