题解 - Codeforces 2039 F1/F2 Shohag Loves Counting

我不会的题，那就是好题。

题意简述

假设有一个数组 $a$，$f(k)$ 表示 $a$ 所有长度为 $k$ 的子区间的最大值的 $\gcd$，$a$ 是好的当且仅当在定义域内 $f(k)$ 两两不同。求有多少个值域为 $[1,m]$ 的整数的任意长度的 $a$ 是好的。对 F1 Easy Version，$\sum m\le 10^5$；对 F2 Hard Version，$m\le 10^6$。

观察

$f(k)$ 两两不同，首先要定长区间最大值集合两两不同。从 $k=2$ 考虑，就是要求 $\nexists i\ \text{s.t.}\ a_i\ge a_{i-1},a_i\ge a_{i+1}$。然后发现对后续的过程还要求 $a_i$ 两两不同。

手动模拟后总结一下：好的序列必须是一个严格单谷序列，并且从小到大排序后，所有后缀 $\gcd$ 两两不同。

Easy Version

既然是后缀，$\sum m$ 也很小，考虑从大到小插入数。令 $f_i$ 维护当前后缀 $\gcd$ 为 $i$ 的序列个数，然后每次长度加一的时候因为最小值有两个位置可以插入（当前最小值的左右），所以 $\times$ 贡献过去。每次插入一个数 $i$，考虑 $f_j$ 向 $f_{\gcd(i,j)}$ 贡献。直接做是 $O(m^2\log m)$。

看到 $\gcd$ 一个想法是莫反。推一推式子，假设当前考虑对 $f_j$ 的增量，且暂且不考虑贡献时 $\gcd(i,j)<j$ 的限制：

$$\begin{aligned}&\sum_k f_k[\gcd(k,i)=j] \\ =& \sum_k f_{jk}[\gcd(k,\frac{i}{j})=1] \\ =& \sum_k f_{jk}\sum_{d|\gcd(k,\frac{i}{j})} \mu(d) \\ =& \sum_{dj|i} \mu(d)\sum_k f_{djk} \\ \end{aligned}$$

实时维护一下 $g_i=\sum_j f_{ij}$，遍历每个 $i$ 的因子 $j$，套一层遍历每个 $\frac{i}{j}$ 的因子 $d$，把 $\mu (d)g_{dj}$ 加入贡献中。最后把限制减掉 $f_j$ 对自身的贡献，这部分的贡献 $\times 2$。然后新建一个点的贡献就是给 $f_i$ 做一次 $+1$。细节上，这些都是同时做的，所以把所有的贡献暂存然后再一起加回去。

单次时间 $O(\sum_{1\le i\le n}\sum_{d|i}\sigma(d))$。

代码：

#include <bits/stdc++.h>
using namespace std;

const int MXN = 100005;
const int DVS = 998244353;
int T, N, cnt[MXN], sum[MXN], ans, delta[MXN], mu[MXN];
vector<int> fac[MXN];

inline void add(int i, int v) {
  cnt[i] = (cnt[i] + v) % DVS;
  for (int j : fac[i]) sum[j] = (sum[j] + v) % DVS;
}

int main() {
  mu[1] = 1;
  for (int i(1); i != MXN; ++i) {
    fac[i].push_back(i);
    for (int j(i + i); j < MXN; j += i) fac[j].push_back(i), mu[j] -= mu[i];
    mu[i] = (DVS + mu[i]) % DVS;
  }
  cin >> T;
  while (T--) {
    cin >> N;
    for (int i(1); i <= N; ++i) cnt[i] = 0, sum[i] = 0;
    for (int i(N); i; --i) {
      for (int j : fac[i]) {
        delta[j] = (DVS - cnt[j]) % DVS;
        for (int k : fac[i / j])
          delta[j] = (delta[j] + mu[k] * 1LL * sum[j * k]) % DVS;
        delta[j] = delta[j] * 2 % DVS;
      }
      delta[i] = (delta[i] + 1) % DVS;
      for (int j : fac[i]) add(j, delta[j]), delta[j] = 0;
    }
    ans = 0;
    for (int i(1); i <= N; ++i) ans = (ans + cnt[i]) % DVS;
    cout << ans << endl;
  }
  return 0;
}

Hard Version

发现强制要求从小往大插，离线存一下答案。

那好吧，令 $f_{i,j}$ 表示当前位的后缀 $\gcd$ 填 $i$，当前位本身是 $ij$。再次考虑莫反算贡献，枚举当前 $i$ 的每个因子 $j$：

$$\begin{aligned} &\sum_{k,l} f_{k,l}[\gcd(kl,j)=k] \\ =& \sum_{k,l} f_{k,l}[\gcd(l,\frac{j}{k})=1] \\ =& \sum_{kd|j} \mu(d) \sum_{l} f_{k,dl} \end{aligned}$$

你以为这里要两维都记然后达成 $O(n\log n)$ 的空间复杂度？不用！只要存 $g_i=\sum_{d|i} \mu(d) \sum_{l} f_{\frac{i}{d},dl}$，每次查询 $g_{kd}$ 即可。复杂度不变。

这么做还是不考虑贡献时 $\gcd(i,j)<j$ 的限制，所以仍然要除去 $s_i=\sum_k f_{i,k}$ 对自身的贡献。那么空间上只存 $g,s$ 两个。空间是 $O(n)$ 的。

每次加入一个数 $i$，对所有 $j|i$ 的 $f_{j,\frac{i}{j}}$ 做更新，而且每个都要 $+1$。而答案的差分即为 $f_{i,1}$，前缀和一下即可。

时间有点紧（虽然我没卡常），可以通过存因数的时候先做 vector::reserve() 加速。

代码：

#include <bits/stdc++.h>
using namespace std;

const int MXN = 1000005;
const int DVS = 998244353;
int T, N, cnt[MXN], sum[MXN], ans[MXN], delta[MXN], mu[MXN];
vector<int> fac[MXN];

inline void add(int i, int v) {
  cnt[i] = (cnt[i] + v) % DVS;
}

int main() {
  mu[1] = 1;
  for (int i(1); i != MXN; ++i) fac[i].reserve(10);
  for (int i(1); i != MXN; ++i) {
    fac[i].push_back(i);
    for (int j(i + i); j < MXN; j += i) fac[j].push_back(i), mu[j] -= mu[i];
    mu[i] = (DVS + mu[i]) % DVS;
  }
  for (int i(1); i != MXN; ++i) {
    for (int j : fac[i]) {
      delta[j] = (DVS - cnt[j]) % DVS;
      for (int k : fac[j]) delta[j] = (delta[j] + sum[k]) % DVS;
      delta[j] = (delta[j] + delta[j] + 1) % DVS;
    }
    for (int j : fac[i]) {
      for (int k : fac[i / j])
        sum[j * k] = (sum[j * k] + mu[k] * 1LL * delta[j]) % DVS;
      cnt[j] = (cnt[j] + delta[j]) % DVS;
    }
    ans[i] = (ans[i - 1] + cnt[i]) % DVS;
  }
  scanf("%d", &T);
  while (T--) scanf("%d", &N), printf("%d\n", ans[N]);
  return 0;
}