pekempey's blog

998244853

AGC 038 C - LCMs

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

この問題を解く前に

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

を求める問題を解く。これは

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

を求めてから包除原理すると求まる。最大公約数よりも公約数の方が解きやすいということ。まず

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

である。$F_k$ は分けられる。

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

これで $F_1, F_2, F_3, \ldots$ は求まった。最後に $f_1, f_2, f_3, \ldots$ に戻す。ここで包除原理を使う。

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

とすればいい。詳しくは

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

である。メビウス関数を使えば

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

とも書ける。

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

AGC 038 D - Unique Path

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

Type 0 has transitivity, that is for all a, b, c, if there is exactly one path between a and b and there is exactly one path between b and c, then there is exactly one path between a and c. So type 0 is an equivalence relation.

For any equivalence relation, we can consider equivalence class. In this problem, each equivalence class forms a tree. It is intuitive, isn't it?

On the other hand, type 1 doesn't have transitivity. For example, in the following figure, a => b and b => c doesn't imply a => c.

f:id:pekempey:20190921233302p:plain

After making trees, connect trees like circle.

f:id:pekempey:20190921233718p:plain

If there are k trees, at least k edges are required to form a circle, and at most k*(k-1)/2 edges can be used optionally.

f:id:pekempey:20190921235031p:plain

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.

f:id:pekempey:20190916232741p:plain:w400

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

f:id:pekempey:20190916234612p:plain:w400

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