[题解] JXOI2018 游戏

Contents

1 题目描述
2 输入格式
3 输出格式
4 样例输入
5 样例输出
6 数据范围及提示
7 解题思路
8 代码

题目描述

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

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

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

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

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

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

输入格式

第一行输入一个整数 $T$ 表示数据组数。每组数据第一行输入一个整数 $n$ 表示数列长度。第二行输入 $n$ 个整数描述颜色序列。

输出格式

对于每组数据输出一个整数表示答案

样例输入

2 4

样例输出

数据范围及提示

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

{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$

解题思路

对于一个需要被检查的区间 $l$ 到 $r$ ，一定是有一些办公室必须被访问的，我们将这些办公室的编号称为关键数，一共有 $sum$ 个

这 $n$ 个数可以在 $O(n \log \log n)$ 的时间内通过普通的线筛筛出来

那么一个方案访问到最后一个关键数的时间就是这个方案的检查时间

枚举最后一个关键数在第 $i$ 个位置，关键数有 $sum$ 个，非关键数有 $n-sum$ 个

在第 $i$ 个位置之后的数都不是关键数，有 ${n-sum \choose n-i} \times (n-i)!$ 种可能

第 $i$ 个数一定是关键数，前 $i-1$ 共有 $(i-1)!$ 种可能

$$
\sum_{i=1}^n i \times (i-1)! \times {n-sum \choose n-i} \times (n-i)!
$$
即为答案

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 10000000 + 10;
const int MOD = 1e9 + 7;

inline int read(){
    int x = 0;
    char ch = getchar();

    while(ch < '0' || ch > '9')
        ch = getchar();

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return x;
}

inline long long powx(long long a, long long b){
    long long ans = 1;
    for(; b; b >>= 1){
        if(b & 1) ans = (ans * a) % MOD;
        a = (a * a) % MOD;
    }
    return ans;
}

long long fac[MAXN], inv[MAXN];
bool vis[MAXN];

inline void init(){
    fac[0] = 1;

    for(register int i=1; i<=10000000; i++){
        fac[i] = fac[i-1] * i % MOD;
    }

    inv[10000000] = powx(fac[10000000], MOD - 2);

    for(register int i=9999999; i >= 0; i--){
        inv[i] = inv[i+1] * (i+1) % MOD;
    }
}

inline long long C(int n, int m){
    if(n < m) return 0;
    return (fac[n] * inv[m] % MOD) * inv[n - m] % MOD;
}

int main(){
    init();

    int l = read();
    int r = read();
    int sum = 0;

    for(register int i=l; i<=r; i++){
        if(!vis[i]){
            ++sum;

            for(register int j=1; i * j <= r; j++){
                vis[i * j] = true;
            }
        }
    }

    int n = r - l + 1;
    long long ans = 0;

    for(register int i=sum; i<=n; i++){
        ans = (ans + i * ((((((sum * fac[i-1]) % MOD) * fac[n-i]) % MOD) * C(n - sum, n - i)) % MOD) % MOD) % MOD;
    }

    printf("%lld\n", ans);
    return 0;
}

BLOG