题号 NC113552
名称 Steps to One
来源 CF1139D
戳我进入往期每日一题汇总贴~
往期每日一题二期题单


\

题解

感谢@Alana33推荐题目，100牛币奖励已发放，如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

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

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目6月16日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴