【好题推荐】Steps to One

Steps to One

题目链接：CF1139D Steps to One

Description

给定一个数列，每次随机选一个 $1$ 到 $m$ 之间的数加到数列的末尾，数列中的所有数的 $gcd=1$ 时停止，求期望长度。
答案对 $1e9+7$ 取模。
数据范围 $1\le m\le 100000$ 。

Solution

考虑概率dp
我们定义 $f_i$ 表示当前所有的数 $gcd=i$ 时，还需要加入的数才能使得 $gcd=1$ 的期望个数。

显然 $f_1=0$ ，并且有 $ans=1+\frac{\sum_{i=1}^{m}f_i}{m}$

解释一下， $+1$ 是因为第一个数没有考虑在内，所以需要枚举第一个数是几，显然 $1$ ~ $m$ 都有 $\frac{1}{m}$ 的概率。

转移式： $f_i=1+\frac{\sum_{j=1}^{m}f_{gcd(i,j)}}{m}$

这样复杂度是 $O(m^2log(m))$ 的，过不了此题。

我们考虑优化转移，首先想到的是枚举 $gcd$ ：

$f_i=1+\frac{\sum_{d|i}f_d \sum_{j=1}^{m}[gcd(i,j)=d]}{m}$

我们考虑优化上面这一团式子。

$\sum_{d|i}f_d \sum_{j=1}^{m/d}[gcd(i/d,j)=1]= \sum_{d|i}f_d \sum_{p|\frac{i}{d}} \mu(p) \lfloor \frac{m}{dp}\rfloor$

令 $T=dp$ ，将 $T$ 提前，得到原式
$ $=\sum_{T|i}\lfloor \frac{m}{T}\rfloor \sum_{d|T}f_d \mu(\frac{T}{d})$ $

带回原式，得到
$ $f_i=1+\frac{\sum_{T|i}\lfloor \frac{m}{T}\rfloor \sum_{d|T}f_d \mu(\frac{T}{d})}{m}$ $

我们令 $g_i=\sum_{d|i}f_d\mu(\frac{i}{d})$ ，
如果我们计算出了 $f_{i}$ ，那么可以在 $O(\frac{m}{i})$ 的复杂度去更新 $g_i$ ，这样复杂度是 $O(nln(n))$ 的。
问题关键是如何求解 $f_i$ ，因为右侧也含有 $f_i$ 的项，所以我们将其分裂：

$f_i=1+\frac{\sum_{T|i}\lfloor \frac{m}{T}\rfloor \sum_{d|T}f_d \mu(\frac{T}{d})[d ≠ i]}{m}+\frac{\lfloor\frac{m}{i}\rfloor f_i}{m}$

化简得：

$f_i=\frac{m+\sum_{T|i}\lfloor \frac{m}{T}\rfloor \sum_{d|T}f_d\mu(\frac{T}{d})[d≠i]}{m-\lfloor \frac{m}{i}\rfloor}$

我们发现上面那团式子跟前面定义的 $g_i$ 有点不同，因为这个式子多了个 $[d≠i]$ 。
但是没关系，因为这个条件只在 $T=i$ 的时候才有限制，而我们在枚举 $T=i$ 时，刚好在第 $i$ 个位置上少了一个 $f_i\mu(1)$ ，所以这个位置是 $0$ ，不影响答案。
所以完美规避了这个问题~
复杂度： $O(nln(n))$ ，可以通过本题。

Code

// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int N = 500005;
const int mod = 1e9 + 7;
vector <int> pr, d[N];
int vis[N], mu[N], inv[N];
void pre(int n) {
  mu[1] = 1; // 预处理mu函数 
  for (int i = 2; i <= n; i++) {
    if (!vis[i]) pr.push_back(i), mu[i] = -1;
    for (auto v: pr) {
      if (i * v > n) break;
      vis[i * v] = 1;
      if (i % v == 0) break;
      mu[i * v] = -mu[i];
    }
  }
  for (int i = 1; i <= n; i++) { // 预处理每个数的因子集合 
    for (int j = i; j <= n; j += i) {
      d[j].push_back(i); 
    }
  }
  inv[1] = 1; // 预处理每个数的逆元 
  for (int i = 2; i <= n; i++) {
    inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
  }
}

int f[N], g[N], m;
int main() {
  scanf("%d", &m);
  pre(m);
  int res = 0;
  f[1] = 0;
  for (int i = 2; i <= m; i++) {
    f[i] = m;
    for (auto T: d[i]) { // 枚举所有的T|i 
      f[i] = (f[i] + 1ll * (m / T) * g[T]) % mod;
    }
    f[i] = 1ll * f[i] * inv[m - (m / i)] % mod;
    //printf("f[%d] = %d\n", i, f[i]);
    res = (res + f[i]) % mod;
    for (int j = i; j <= m; j += i) { // 更新所有的g[i] 
      g[j] = (g[j] + 1ll * f[i] * mu[j / i]) % mod;
    }
  }
  res = 1ll * res * inv[m] % mod;
  res++;
  printf("%d\n", (res % mod + mod) % mod);
  return 0;
}