P4562 [JXOI2018]游戏

佚名 5年前 (2019-03-12) 算法 991人围观抢沙发百度已收录

题面

题目描述

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

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

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

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

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

2 4

输出样例#1：

\(\text{Solution:}\)

考虑到一个数能对答案有贡献，那么它一定不是其它数的倍数，假设这样的数有sum个。

对于九条可怜任意选择的排列，那么答案就是排列中最靠后的不能被其它数表示出来的数的位置。

所以我们可以枚举最靠后的那个数的位置 \(i\) ，\(i\) 位置可以选择 \(sum\) 个数中的任何一个数，而对于 \(i\) 后面的数它们是从 \(n-sum\) 个数中选出的 \(n-i\) 个数，而且可以随意排列，\(i\) 之前的数也可以随意排列，所以我们就有了一个用一堆乘法原理推出来的式子：

\[\begin{aligned} Ans=\sum_{i=sum}^{n}i \times sum \times C_{n-sum}^{n-i} \times (n-i)! \times (i-1)! \end{aligned} \]

#include <set>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <assert.h>
#include <algorithm>

using namespace std;

#define fir first
#define sec second
#define pb push_back
#define mp make_pair
#define LL long long
#define INF (0x3f3f3f3f)
#define mem(a, b) memset(a, b, sizeof (a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(x) cout << #x << " = " << x << endl
#define travle(i, x) for (register int i = head[x]; i; i = nxt[i])
#define For(i, a, b) for (register int (i) = (a); (i) <= (b); ++ (i))
#define Forr(i, a, b) for (register int (i) = (a); (i) >= (b); -- (i))
#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define ____ debug("go\n")

namespace io {
    static char buf[1<<21], *pos = buf, *end = buf;
    inline char getc()
    { return pos == end && (end = (pos = buf) + fread(buf, 1, 1<<21, stdin), pos == end) ? EOF : *pos ++; }
    inline int rint() {
        register int x = 0, f = 1;register char c;
        while (!isdigit(c = getc())) if (c == '-') f = -1;
        while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getc()));
        return x * f;
    }
    inline LL rLL() {
        register LL x = 0, f = 1; register char c;
        while (!isdigit(c = getc())) if (c == '-') f = -1;
        while (x = (x << 1ll) + (x << 3ll) + (c ^ 48), isdigit(c = getc()));
        return x * f;
    }
    inline void rstr(char *str) {
        while (isspace(*str = getc()));
        while (!isspace(*++str = getc()))
            if (*str == EOF) break;
        *str = '\0';
    }
    template<typename T> 
        inline bool chkmin(T &x, T y) { return x > y ? (x = y, 1) : 0; }
    template<typename T>
        inline bool chkmax(T &x, T y) { return x < y ? (x = y, 1) : 0; }    
}
using namespace io;

const int N = 1e7 + 10, P = 1e9 + 7;
int fac[N], ifac[N];
int qpow(int a, int b) 
{
    int res = 1;
    while (b) 
    {
        if (b & 1) res = 1ll * a * res % P;
        a = 1ll * a * a % P;
        b >>= 1;
    }
    return res;
}
void init(int n) 
{
    fac[0] = 1;
    for (int i = 1; i <= n; ++ i)
        fac[i] = 1ll * fac[i - 1] * i % P;
    ifac[n] = qpow(fac[n], P - 2);
    for (int i = n - 1; i >= 0; -- i) 
        ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
}
int C(int n, int m) 
{
    if (n < m) return 0;
    return 1ll * fac[n] % P * 1ll * ifac[m] % P * 1ll * ifac[n - m] % P;
}
bool vis[N];
int main() {
#ifndef ONLINE_JUDGE
    file("P4562");
#endif
    int n, L, R, sum = 0;
    cin >> L >> R;
    n = R - L + 1;
    init(R);
    for (int i = L; i <= R; ++ i)
    {
        if (!vis[i]) sum++;
        for (int j = i + i; j <= R; j += i)
            vis[j] = true;
    }
    int ans = 0;
    for (int i = sum; i <= n; ++ i)
        ans = (ans + 1ll * i * fac[i - 1] % P * sum % P * C(n - sum, n - i) % P * fac[n - i] % P) % P;
    cout << ans << endl;
}