CF1139D Steps to One

期望+莫比乌斯反演。

期望的题，每次都这么神秘啊。

Solution

首先我们先把式子写出来，令$E$是期望，$P$是概率。
$$\begin{array}{rl}E(len)& =\sum _{i\ge 1}P(len=i)\cdot i\\ & =\sum _{i\ge 1}P(len=i)\sum _{j=1}^i\\ & =\sum _{j\ge 1}\sum _{i\ge j}P(len=i)\\ & =\sum _{i\ge 1}P(len\ge i)\\ & =1+\sum _{i\ge 1}P(len>i)\end{array}$$
最后的状态是$\underset{i=1}{\overset{len}{gcd}}{a}_i=1$，于是又可推得：
$$\begin{array}{rl}P(len>i)& =P((\underset{j=1}{\overset{i}{gcd}}{a}_i)>1)\\ & =1-P((\underset{j=1}{\overset{i}{gcd}}{a}_i)=1)\\ & =1-\frac{\sum _{a_1=1}^m\sum _{a_2=1}^m\cdots \sum _{a_n=1}^m\sum _{d|\underset{j=1}{\overset{m}{gcd}}{a}_j}\mu (d)}{m^i}\\ & =1-\frac{\sum _{d=1}^m\mu (d){\lfloor \frac{m}{d}\rfloor }^i}{m^i}\\ & =\frac{\sum _{d=2}^m\mu (d){\lfloor \frac{m}{d}\rfloor }^i}{m^i}\end{array}$$
再带回原式可得：
$$\begin{array}{rl}E(len)& =1+\sum _{i\ge 1}P(len>i)\\ & =1-\sum _{i\ge 1}\frac{\sum _{d=2}^m\mu (d){\lfloor \frac{m}{d}\rfloor }^i}{m^i}\\ & =1-\sum _{d=2}^m\mu (d)\sum _{i\ge 1}(\frac{\lfloor \frac{m}{d}\rfloor }{m}{)}^i\\ & =1-\sum _{d=2}^m\mu (d)\frac{\lfloor \frac{m}{d}\rfloor }{m-\lfloor \frac{m}{d}\rfloor }\end{array}$$
关于最后一步是生成函数的无限项求值。

Code

#include<bits/stdc++.h>
#include<algorithm>
#define LL long long
#define PII pair<LL, int>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void out(T res)
{
    if(res > 9) out(res / 10);
    putchar(res % 10 + '0');
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    out(res);
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(const char *s){ while(*s) putchar(*s ++); } 
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); }
const int N = 1e5 + 5, mod = 1e9 + 7;
int n;
int mu[N], primes[N], cnt, st[N], inv[N];
void init()
{
    mu[1] = 1;
    for(int i = 2;i < N;i ++)
    {
        if(!st[i]) primes[++ cnt] = i, mu[i] = -1;
        for(int j = 1;j <= cnt && primes[j] * i < N;j ++)
        {
            st[primes[j] * i] = 1;
            if(i % primes[j] == 0) 
            {
                mu[primes[j] * i] = 0;
                break;
            }
            mu[primes[j]* i] = -mu[i];
        }
    }
    inv[1] = 1;
    for(int i = 2;i < N;i ++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
}
int ans;
int main()
{
    read(n);
    init();
    ans = 1;
    for(int i = 2;i <= n;i ++)
        ans = (ans - 1ll * mu[i] % mod * (n / i) % mod * inv[n - n / i] % mod) % mod, ans = (ans + mod) % mod;
    write(ans);
    return 0;
}