Codeforces #548 (Div. 2) D. Steps to One

题目链接 https://codeforces.com/contest/1139/problem/D

f(k) 表示 a[1],...,a[k] 的最大公约数不是 1 的概率。然后答案是 1+f(1)+f(2)+f(3)+...。a[1],...,a[n] 的最大公约数是 1 和 a[1],...,a[k] 不能被 2,3,4,... 整除等价。所以由容斥原理可以计算 f(k)。

f(k,p) 是前 k 项是 p 的倍数的概率。

\begin{align}
\textit{answer} &= 1 - \sum_{k=1}^{\infty} \sum_{p=2}^{\infty} \mu(p) f(k,p) \\
&= 1 - \sum_{p=2}^{\infty} \mu(p) \sum_{k=1}^{\infty} f(k,p) \\
&= 1 - \sum_{p=2}^{\infty} \mu(p) \sum_{k=1}^{\infty} \heartsuit^k \\
&= 1- \sum_{p=2}^{\infty} \mu(p) \frac{\heartsuit}{1-\heartsuit}
\end{align}

如果不用默比乌斯函数，答案能写成以下。这里的 p, q, r, ... 走所有质数上。

\begin{align}
1+\sum_{k=1}^{\infty} \left(\sum_{p} f(k,p) - \sum_{p < q} f(k,pq) + \sum_{p < q < r} f(k,pqr) - \cdots \right)
\end{align}

yukicoder no. 803 Very Limited Xor Subset

https://yukicoder.me/problems/no/803

Once we realize this problem is related to a system of linear equations, this problem has been almost solved. All we have to do is to find the number of solutions of the given linear system.

Let u be a solution of Ax=b and v be a solution of Ax=0. Then u+v is also a solution. Actually, any solution can be written as u+v where v is a solution of Ax=0. So, the number of solutions of Ax=0 is equal to the number of solutions of Ax=b unless Ax=b has no solutions. The set of solutions of Ax=0 is called the kernel, denoted by ker A. In fact, ker A forms a vector space. Thus, if we know the dimension of ker A, we can find out the number of elements contained in ker A. The dimension of ker A can be computed by the rank–nullity theorem (also known as the dimension theorem.) This theorem says dim ker A + dim im A = N. So if we have the rank of A (=dim im A), we can solve this problem immediately.

yukicoder 802 だいたい等差数列

https://yukicoder.me/problems/no/802

Let us find the number of \(x_1, \ldots, x_N\) such that \(x_1 + \cdots + x_N \le M\) and \( x_1 \ge 0\), \(0 \le x_i \le D_2-D_1 \) for \(2\le i \le N\). The generating function can be written as

\begin{align}
(1+x+\cdots+x^{D_2-D_1})^{N-1} \times (1+x+x^2+x^3+x^4+\cdots)^2.
\end{align}

Thus, the answer is

\begin{align}
[x^M] \left( \frac{(1-x^{D_2-D_1+1})^{N-1}}{(1-x)^{N+1}} \right).
\end{align}

The coefficient of \(1/(1-x)^n\) can be computed quickly using the H(n,r). I think inclusion exclusion is simpler than this.

AtCoder Grand Contest 031 D: A Sequence of Permutations

https://atcoder.jp/contests/agc031/tasks/agc031_d

This article is almost the same as the official editorial. I just want to write English and Chinese (A month has passed since I started learning Chinese. If you cannot read my Chinese, I'm sorry.)
我的说明和正式的说明很相像。我刚想写英文和中文。如果你不能理解我的中文，对不起。

The key idea is a permutation can be treated as a bijection. If we treat them as bijections, we can write f(a[n], a[n+1]) as a[n+1]a[n]^-1.
因为我们能吧全排列当做双射，所以 f(a[n],a[n+1]) 可以写成 a[n+1]a[n]^-1。

Then, let us make a list of a[n]. In this program, the inverse of p is denoted by P.
然后，枚举 a[n]。这个程序中 P 是 p 的逆元素。

def reduce(s)
  loop do
    t = s.gsub('pP', '')
         .gsub('Pp', '')
         .gsub('qQ', '')
         .gsub('Qq', '')
    break if s == t
    s = t
  end
  s
end

def inverse(f)
  f.reverse.swapcase
end

s = ['p', 'q']
(2..40).each do |i|
  s[i] = reduce(s[i - 1] + inverse(s[i - 2]))
end

s.each do |x|
  puts x
end

p
q
qP
qPQ
qPQpQ
qPQppQ
qPQpqpQ
qPQpqPqpQ
qPQpqPPqpQ
qPQpqPQPqpQ
qPQpqPQpQPqpQ
qPQpqPQppQPqpQ
qPQpqPQpqpQPqpQ
qPQpqPQpqPqpQPqpQ
qPQpqPQpqPPqpQPqpQ
qPQpqPQpqPQPqpQPqpQ
qPQpqPQpqPQpQPqpQPqpQ
qPQpqPQpqPQppQPqpQPqpQ
qPQpqPQpqPQpqpQPqpQPqpQ
qPQpqPQpqPQpqPqpQPqpQPqpQ
qPQpqPQpqPQpqPPqpQPqpQPqpQ
qPQpqPQpqPQpqPQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQppQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQppQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPQPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPQpQPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPQppQPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPQpqpQPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPQpqPqpQPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPQpqPPqpQPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPQpqPQPqpQPqpQPqpQPqpQPqpQPqpQ
qPQpqPQpqPQpqPQpqPQpqPQpqPQpQPqpQPqpQPqpQPqpQPqpQPqpQ

We can see that qPQp and PqpQ appears repeatedly, and this sequence has the period of length 6. The power of the bijection can be achieved by O(log n) times composition, thus this problem is solved.
我们可以看很多的 qPQp 和 PqpQ 在 a[i] 里。双射的幂能实现 O(N log N) 的复杂度。所以我们得到答案了。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); i++)

struct perm {
  vector<int> a;
  perm(int n) : a(n) {}
  int size() { return a.size(); }
  int &operator[](int k) { return a[k]; }
};

perm operator*(perm a, perm b) {
  const int n = a.size();
  perm ans(n);
  REP(i, n) ans[i] = a[b[i]];
  return ans;
}

perm inv(perm a) {
  const int n = a.size();
  perm ans(n);
  REP(i, n) ans[a[i]] = i;
  return ans;
}

perm pow(perm a, int b) {
  const int n = a.size();
  perm ans(n);
  REP(i, n) ans[i] = i;
  while (b > 0) {
    if (b & 1) ans = ans * a;
    a = a * a;
    b >>= 1;
  }
  return ans;
}

void print(perm a) {
  for (int i = 0; i < a.size(); i++) {
    if (i > 0) cout << ' ';
    cout << a[i] + 1;
  }
  cout << '\n';
}

int main() {
  int N, K;
  cin >> N >> K;
  perm P(N), Q(N);
  REP(i, N) cin >> P[i], P[i]--;
  REP(i, N) cin >> Q[i], Q[i]--;
  auto X = Q * inv(P) * inv(Q) * P;
  auto Y = inv(P) * Q * P * inv(Q);
  vector<perm> A;
  A.push_back(P);
  A.push_back(Q);
  for (int i = 0; i < 5; i++) {
    A.push_back(A[i + 1] * inv(A[i]));
  }
  A.erase(A.begin());
  if (K == 1) {
    print(P);
    return 0;
  }
  K -= 2;
  perm ans = pow(X, K / 6) * A[K % 6] * pow(Y, K / 6);
  print(ans);
}

I love this problem.
我喜欢这道题。

Codeforces Round #546 (Div. 2) E. Nastya Hasn't Written a Legend

https://codeforces.com/contest/1136/problem/E

If we have a segment tree which can perform the following operations, we can directly solve this problem.

1. For $l \le i \le r$, $A_i \gets \max(A_i, x)$
2. For $l \le i \le r$, $A_i \gets A_i + x$
3. Compute $A_l + \cdots + A_r$.

This segment tree can be achieved by segment tree beats. https://codeforces.com/blog/entry/57319

Of course, we can solve this problem by simply maintaining the intervals taking the same values. However, this approach also requires an advanced data structure which can handle range add (or fill) and range sum.

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

const int U = 1 << 17;
const long long INF = 1e18;
long long SUM[U * 2];
long long SIZE[U * 2];
long long MIN[U * 2];
long long MAX[U * 2];
long long FILL[U * 2];

void apply(int k, long long v) {
  SUM[k] = SIZE[k] * v;
  MIN[k] = v;
  MAX[k] = v;
  FILL[k] = v;
}

void push(int k) {
  if (FILL[k] == INF) return;
  apply(k * 2 + 0, FILL[k]);
  apply(k * 2 + 1, FILL[k]);
  FILL[k] = INF;
}

void pull(int k) {
  SUM[k] = SUM[k * 2] + SUM[k * 2 + 1];
  MIN[k] = min(MIN[k * 2], MIN[k * 2 + 1]);
  MAX[k] = max(MAX[k * 2], MAX[k * 2 + 1]);
}

void update(int l, int r, long long v, int k = 1, int x = 0, int y = U) {
  if (y <= l || r <= x) return;
  if (l <= x && y <= r && MIN[k] >= v) return;
  if (l <= x && y <= r && MAX[k] <= v) {
    apply(k, v);
    return;
  }
  push(k);
  update(l, r, v, k * 2 + 0, x, x + y >> 1);
  update(l, r, v, k * 2 + 1, x + y >> 1, y);
  pull(k);
}

long long query(int l, int r, int k = 1, int x = 0, int y = U) {
  if (y <= l || r <= x) return 0;
  if (l <= x && y <= r) return SUM[k];
  push(k);
  long long u = query(l, r, k * 2 + 0, x, x + y >> 1);
  long long v = query(l, r, k * 2 + 1, x + y >> 1, y);
  return u + v;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<long long> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  vector<long long> K(N + 1);
  for (int i = 0; i < N - 1; i++) {
    cin >> K[i + 1];
  }
  for (int i = 0; i < N; i++) {
    K[i + 1] += K[i];
    SUM[i + U] = A[i] - K[i];
    MIN[i + U] = A[i] - K[i];
    MAX[i + U] = A[i] - K[i];
  }
  vector<long long> KS(N + 1);
  for (int i = 0; i < N; i++) {
    KS[i + 1] = KS[i] + K[i];
  }
  for (int i = 0; i < U; i++) {
    SIZE[i + U] = 1;
    FILL[i] = INF;
  }
  for (int i = U - 1; i >= 1; i--) {
    SIZE[i] = SIZE[i * 2] * 2;
    pull(i);
  }
  int Q;
  cin >> Q;
  while (Q--) {
    char t;
    cin >> t;
    if (t == '+') {
      int k, x;
      cin >> k >> x;
      k--;
      long long v = query(k, k + 1) + x;
      update(k, U, v);
    } else {
      int l, r;
      cin >> l >> r;
      l--;
      cout << query(l, r) + KS[r] - KS[l] << '\n';
    }
  }
}