CF1139D Steps to One

tony102

2021 年 08 月 20 日

1705 次浏览

暂无评论

1763字数

题解

[Link](https://www.luogu.com.cn/problem/CF1139D)

## Sol

设 $len$ 为随机出来的一个序列长度。

$$E(len) = \sum\limits_{i \geq 1} P(len = i) \times i$$

$$E(len) = \sum\limits_{i \geq 1} P(len = i) \sum\limits_{j=1}^{i} 1$$

$$E(len) = \sum\limits_{j \geq 1} \sum\limits_{i \geq j} P(len = i) = \sum\limits_{i \geq 1} P(len \geq i) = 1 + \sum\limits_{i \geq 1} P(len > i)$$

现在来处理后面的 $\sum\limits_{i \geq 1} P(len > i)$

$$P(len > i) = P((gcd_{j=1}^{i} a_i) > 1)$$

> 阴阳师：“正难则反”

$$P(len > i) = 1 - P((gcd_{j=1}^{i} a_i) = 1)$$

对于序列中的每一个数，其实都可以枚举它们是 $[1,m]$ 中的哪一个，再除掉 $m^i$ 为 $i$ 个球放在 $m$ 个标有数字的盒子中，且允许有数字没出现过的总方案数。

$$lsh = \frac{\sum_{a_1 = 1}^{m}\sum_{a_2 = 1}^{m}\cdots \sum_{a_{i} = 1}^{m} \epsilon(gcd_{j=1}^{i} a_j)}{m^i} $$

对最后一层的求和符号使用莫比乌斯反演

$$lsh = \frac{\sum_{a_1 = 1}^{m}\sum_{a_2 = 1}^{m}\cdots \sum_{a_{i} = 1}^{m}\sum_{d|(gcd_{j = 1}^{i} a_j)} \mu(d)}{m^i} $$

对每一层都莫比乌斯反演，把枚举的 $d$ 提到最前面去

$$lsh = 1 - \frac{\sum_{d=1}^{m} \mu(d)\sum_{a_1=1}^{m} [d|a_1] \cdots}{m^i}$$

后面的部分上指标同时除以 $d$ 之后可以直接拿出来

$$lsh = \frac{\sum_{d=1}^{m} \mu(d) (\lfloor \frac{m}{d} \rfloor)^i}{m^i}$$

$$lsh = 1 - \frac{\sum_{d=2}^{m} \mu(d) (\lfloor \frac{m}{d} \rfloor)^i}{m^i}$$

所以带回原式可得：

$$1 - \frac{1}{m^i} \sum\limits_{i \geq 1}\sum\limits_{d=2}^{m} \mu(d)(\lfloor \frac{m}{d} \rfloor)^i$$

整除分块：

$$1-\sum\limits_{d = 2}^{m} \mu(d)\frac{\lfloor \frac{m}{d} \rfloor}{m - \lfloor \frac{m}{d} \rfloor}$$

马老师告诉你，后面那一坨类似于杜教筛预处理即可。

## Code

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 2e5 + 5;
const int mod = 1e9 + 7;

int m, tot;
int isnPri[SIZE], pri[SIZE], mu[SIZE], inv[SIZE];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

int qPow(int a, int b) {
    int ans = 1ll;
    for ( ; b; b >>= 1, a = a * a % mod) {
        if (b & 1) ans = ans * a % mod;
    }
    return ans % mod;
}

void init() {
    isnPri[1] = mu[1] = 1;
    for (int i = 2; i <= m + 1; ++ i) {
        if (!isnPri[i]) pri[++ tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot && i * pri[j] <= m + 1; ++ j) {
            isnPri[i * pri[j]] = 1;
            if (i % pri[j]) mu[i * pri[j]] = -mu[i];
            else { mu[i * pri[j]] = 0; break; }
        }
    }
    inv[1]=1;
    for (int i = 2; i <= m + 1; ++ i) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}

signed main() {
    m = read(); init();
    int ans = 1ll;
    for (int i = 2; i <= m + 1; ++ i) ans = (ans - (mu[i] * (m / i) % mod * inv[m - m / i] % mod) + mod) % mod;
    printf("%lld\n", ans % mod);
    return 0;
}
```

最后修改：2021 年 08 月 20 日