P4562 [JXOI2018]游戏

    • 365通过
    • 979提交
  • 题目提供者 Kamila
  • 评测方式 云端评测
  • 标签 数论,数学 期望 组合数学 各省省选 2018
  • 难度 省选/NOI-
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    九条可怜是一个富有的女孩子。

    题目描述

    她长大以后创业了,开了一个公司。 但是管理公司是一个很累人的活,员工们经常背着可怜偷懒,可怜需要时不时对办公室进行检查。

    可怜公司有 $n$ 个办公室,办公室编号是 $l$ 到 $l+n-1$ ,可怜会事先制定一个顺序,按照这个顺序依次检查办公室。一开始的时候,所有办公室的员工都在偷懒,当她检查完编号是 $i$ 的办公室时候,这个办公室的员工会认真工作,并且这个办公室的员工通知所有办公室编号是 $i$ 的倍数的办公室,通知他们老板来了,让他们认真工作。因此,可怜检查完第 $i$ 个办公室的时候,所有编号是 $i$ 的倍数(包括 $i$ )的办公室的员工会认真工作。

    可怜发现了员工们通风报信的行为,她发现,对于每种不同的顺序 $p$ ,都存在一个最小的 $t(p)$ ,使得可怜按照这个顺序检查完前 $t(p)$ 个办公室之后,所有的办公室都会开始认真工作。她把这个 $t(p)$ 定义为 $p$ 的检查时间。

    可怜想知道所有 $t(p)$ 的和。

    但是这个结果可能很大,她想知道和对 $10^9+7$ 取模后的结果。

    输入输出格式

    输入格式:

    第一行输入两个整数 $l,r$ 表示编号范围,题目中的 $n$ 就是 $r-l+1$ 。

    输出格式:

    一个整数,表示期望进行的轮数。

    输入输出样例

    输入样例#1: 复制
    2 4
    输出样例#1: 复制
    16
    

    说明

    样例解释

    考虑所有办公室被检查的相对顺序:

    {2 3 4} ,时间是 2 。 {3 2 4} ,时间是 2 。 {4 2 3} ,时间是 3 。 {4 3 2} ,时间是 3 。 {2 4 3} ,时间是 3 。 {3 4 2} ,时间是 3 。

    和是 $16$ 。

    数据范围

    对于 20% 的数据,$r-l+1\leq 8$。
    对于另 10% 的数据,$l=1$。
    对于另 10% 的数据,$l=2$。
    对于另 30% 的数据,$l\leq 200$。
    对于 100% 的数据,$1\leq l\leq r\leq 10^7$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。