Steps to One

题目链接:CF1139D Steps to One

Description

给定一个数列,每次随机选一个 之间的数加到数列的末尾,数列中的所有数的 时停止,求期望长度。
答案对取模。
数据范围

Solution

考虑概率dp
我们定义表示当前所有的数 时,还需要加入的数才能使得的期望个数。

显然,并且有

解释一下,是因为第一个数没有考虑在内,所以需要枚举第一个数是几,显然~都有的概率。

转移式:

这样复杂度是的,过不了此题。

我们考虑优化转移,首先想到的是枚举

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

,将提前,得到原式
$$

带回原式,得到
$$

我们令
如果我们计算出了,那么可以在的复杂度去更新,这样复杂度是的。
问题关键是如何求解,因为右侧也含有的项,所以我们将其分裂:

化简得:

我们发现上面那团式子跟前面定义的有点不同,因为这个式子多了个
但是没关系,因为这个条件只在的时候才有限制,而我们在枚举时,刚好在第个位置上少了一个,所以这个位置是,不影响答案。
所以完美规避了这个问题~
复杂度:,可以通过本题。

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