CF1139D Steps to One 题解【莫比乌斯反演】【枚举】【DP】

Stella981
• 阅读 323

反演套 DP 的好题(不用反演貌似也能做

Description

Vivek initially has an empty array $a$ and some integer constant $m$.

He performs the following algorithm:

  1. Select a random integer $x$ uniformly in range from $1$ to $m$ and append it to the end of $a$.
  2. Compute the greatest common divisor of integers in $a$.
  3. In case it equals to $1$, break
  4. Otherwise, return to step $1$.

Find the expected length of $a$. It can be shown that it can be represented as $\frac PQ$ where $P$ and $Q$ are coprime integers and $Q\neq 0\pmod{10^9+7}$. Print the value of $P\cdot Q^{-1}\pmod{10^9+7}$.

Input

The first and only line contains a single integer $m$($1\le m\le 100000$).

Output

Print a single integer — the expected length of the array $a$ written as $P\cdot Q^{-1}\pmod{10^9+7}$.

Examples

input

1

output

1

input

2

output

2

input

4

output

333333338

Note

In the first example, since Vivek can choose only integers from $1$ to $1$, he will have $a=[1]$ after the first append operation, and after that quit the algorithm. Hence the length of $a$ is always $1$, so its expected value is $1$ as well.

In the second example, Vivek each time will append either $1$ or $2$, so after finishing the algorithm he will end up having some number of $2$'s (possibly zero), and a single $1$ in the end. The expected length of the list is $1⋅\frac 12+2⋅\frac 1{2^2}+3⋅\frac 1{2^3}+\dots =2$.

题意

每一步在 $1\sim m$ 中任选一个整数,问期望多少步后选出的数的最大公约数是 $1$。答案对 $1\ 000\ 000\ 007$ 取模。

题解

因为每一步不会让已经选了的元素的 $\gcd$ 和变大,因此认为是一个除自环外的有向无环图。对于自环我们很好处理,所以把它看成是一道期望 DP。

令 $f[i]$ 表示当前的 $\gcd$ 和为 $i$,到 $\gcd$ 和为 $1$ 的状态的期望步数。因此把状态转移方程写出来 $$ f[i]=1+\frac{\sum_{j=1}^m f[\gcd(i,j)]}m $$ 这样的转移是 $O(m^2)$ 的。但是我们发现,对于很多 $j$,$\gcd(i,j)$ 都是相等的,因此我们把这样的数整合到一起。

令 $F(n)$ 表示 $1\sim m$ 中有多少个数 $i$ 满足 $\gcd(x,i)=n$,其中视 $x​$ 为常数。

则计算 $f[i]$ 就转化为了 $$ f[i]=1+\frac{\sum_{d|i}f[d]\times F(d)}n,x=i $$ 这样差不多就把枚举优化到了 $\log n$ 的 $d|i​$。

考虑怎么计算 $F(n)$ $$ F(n)=\sum_{i=1}^m[\gcd(x,i)=n] $$ 令 $G(n)=\sum_{n|d}F(d)$,则 $$ \begin{aligned} G(n)&=\sum_{n|d}F(d)\ &=\sum_{n|d}\sum_{i=1}^m[\gcd(x,i)=d]\ &=\sum_{i=1}^m[n|\gcd(x,i)]\ ?&=\sum_{i=1}^{\left\lfloor\frac mn\right\rfloor}\left[1|\gcd\left(\frac xn,i\right)\right] \end{aligned} $$ 实际上这样是有问题的,因为(在后面)无法保证 $n|x$,此时 $G(n)$ 就一定为 $0$ 了。

我们再多化一步: $$ \begin{aligned} G(n)&=\sum_{i=1}^{\left\lfloor\frac mn\right\rfloor}\left[1|\gcd\left(\frac xn,i\right)\right][n|x]\ &=\left\lfloor\frac mn\right\rfloor\cdot[n|x] \end{aligned} $$ 根据 $G(n)=\sum_{n|d}F(d)$,我们反演到 $F$,得 $$ \begin{aligned} F(n)&=\sum_{n|d}\mu\left(\frac dn\right)G(d)\ &=\sum_{i=1}^{\left\lfloor\frac mn\right\rfloor}\mu(i)G(ni)\ &=\sum_{i=1}^{\left\lfloor\frac mn\right\rfloor}\mu(i)\left\lfloor\frac{m}{ni}\right\rfloor[(ni)|x] \end{aligned} $$ 我们发现后面的布尔表达式可以当作条件。原本的条件本来就是 $\to +\infty$ 的,只不过超过了 $\left\lfloor\frac mn\right\rfloor$ 没有意义。因此直接把条件换成 $[(ni)|x]$ 即可。又因为 $n|x$ 在上面的枚举过程中是成立的,同时可以转化为 $\left[i|\frac xn\right]$。 $$ F(n)=\sum_{i|\frac xn}\mu(i)\left\lfloor\frac{m}{ni}\right\rfloor $$ 这样的一次枚举是 $O\left(d\left(\frac xn\right)\right)$ 的,由于 $1\sim m$ 的约数个数和均摊是 $O(\log m)$ 的,其中最多的有 $128$ 个约数,但是这样的数肯定不是很多,并且其中很多被枚举到的数都是质因数,迭代一下并不会造成很大的复杂度。

然后我们需要再把状态转移方程稍微转化一下,把 $f[i]$ 移到左边 $$ \begin{aligned} f[i]&=1+\frac{\sum_{d|i,d<i}f[d]\times F(d)+f[i]\times F(i)}n,x=i\ \frac{n-F(i)}{n}\cdot f[i]&=1+\frac{\sum_{d|i,d<i}f[d]\times F(d)}n,x=i\ f[i]&=\frac{n+\sum_{d|i,d<i}f[d]\times F(d)}{n-F(i)},x=i \end{aligned} $$ 就得到了真正的转移方程。

时间复杂度 $O(m\log^2 m)$。

Code:

#include<cstdio>
#include<cstring>
#include<vector>
#define ll long long
#define p 1000000007
using std::vector;
vector<int> v[100100];//约数用 vector 存一下,每次 √m 枚举不是很稳
ll qpow(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1)
            ans=ans*x%p;
        x=x*x%p;
        y>>=1;
    }
    return ans;
}
bool is[100100];
int pri[100100],mu[100100],cnt=0;
ll f[100100];
int n;
int calc(int x,int y)//1~n 中 gcd(x,i)=y 的数的个数
{
    int g=x/y,ans=0;
    for(int i=0;i<v[g].size();++i)
        ans+=mu[v[g][i]]*(n/v[g][i]/y);
    return ans;
}
int main()
{
    scanf("%d",&n);
    f[1]=1;
    mu[1]=1;
    for(int i=2;i<=n;++i)
    {
        if(!is[i])
        {
            pri[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&i*pri[j]<=n;++j)
        {
            is[i*pri[j]]=1;
            if(i%pri[j])
                mu[i*pri[j]]=-mu[i];
            else
            {
                mu[i*pri[j]]=0;
                break;
            }
        }
    }
    for(int i=1;i<=n;++i)
        for(int j=i;j<=n;j+=i)
            v[j].push_back(i);
    ll ans=1,inv=qpow(n,p-2);
    for(int i=2;i<=n;++i)
    {
        for(int j=0;j<v[i].size()-1;++j)
            f[i]=(f[i]+calc(i,v[i][j])*f[v[i][j]]%p)%p;
        f[i]=(f[i]*inv+1)%p;
        ll g=n-calc(i,i);
        f[i]=f[i]*n%p*qpow(g,p-2)%p;
        ans=(ans+f[i])%p;
    }
    printf("%lld\n",ans*qpow(n,p-2)%p);
    return 0;
}
点赞
收藏
评论区
推荐文章
Jacquelyn38 Jacquelyn38
1年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。 1、使用解构获取json数据let jsonData   id: 1, status: "OK", data: ['a', 'b'] ; let  id, status, data: number   jsonData; console.log(id, status, number )
刚刚好 刚刚好
2个月前
css问题
1、 在IOS中图片不显示(给图片加了圆角或者img没有父级) <div<img src""/</div div {width: 20px; height: 20px; borderradius: 20px; overflow: h
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录 问题 用navicat导入数据时,报错: 原因这是因为当前的MySQL不支持datetime为0的情况。 解决修改sql\mode: sql\mode:SQL Mode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。 全局s
晴空闲云 晴空闲云
2个月前
css中box-sizing解放盒子实际宽高计算
我们知道传统的盒子模型,如果增加内边距padding和边框border,那么会撑大整个盒子,造成盒子的宽度不好计算,在实务中特别不方便。boxsizing可以设置盒模型的方式,可以很好的设置固定宽高的盒模型。 盒子宽高计算假如我们设置如下盒子:宽度和高度均为200px,那么这会这个盒子实际的宽高就都是200px。但是当我们设置这个盒子的边框和内间距的时候,那
艾木酱 艾木酱
1个月前
快速入门|使用MemFire Cloud构建React Native应用程序
> MemFire Cloud是一款提供云数据库,用户可以创建云数据库,并对数据库进行管理,还可以对数据库进行备份操作。它还提供后端即服务,用户可以在1分钟内新建一个应用,使用自动生成的API和SDK,访问云数据库、对象存储、用户认证与授权等功能,可专
Wesley13 Wesley13
1年前
MySQL查询按照指定规则排序
1.按照指定(单个)字段排序 select * from table_name order id desc; 2.按照指定(多个)字段排序 select * from table_name order id desc,status desc; 3.按照指定字段和规则排序 selec
Stella981 Stella981
1年前
Angular material mat
Icon Icon Name mat-icon code _add\_comment_ add comment icon <mat-icon> add\_comment</mat-icon> _attach\_file_ attach file icon <mat-icon> attach\_file</mat-icon> _attach\
Wesley13 Wesley13
1年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
#### 背景描述 # Time: 2019-01-24T00:08:14.705724+08:00 # User@Host: **[**] @ [**] Id: ** # Schema: sentrymeta Last_errno: 0 Killed: 0 # Query_time: 0.315758 Lock_
helloworld_34035044 helloworld_34035044
4个月前
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。 uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid() 或 uuid(sep)参数说明:sep 布尔值,生成的uuid中是否包含分隔符'',缺省为
helloworld_28799839 helloworld_28799839
2个月前
常用知识整理
# Javascript ## 判断对象是否为空 ```js Object.keys(myObject).length === 0 ``` ## 经常使用的三元运算 > 我们经常遇到处理表格列状态字段如 `status` 的时候可以用到 ``` vue