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

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

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

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

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

链接 🔗

「JXOI2018」游戏

题解 ❓

有一些是必须点
每个排列的花费等于这个排列的必须点最后的位置 (埃式筛)
然后考虑组合数方式,枚举最后一个点在第i位时的方案数,设必须点个数为kk
则方案数为

A(n1)(k1)k(nk)!A_(n-1)^(k-1) * k * (n-k)!

代码

const double eps = 1e-8;
const int mod = 1e9+7;
const int N = 1e7+1;
int fac[N],inv[N],Finv[N];
struct
{
    void init()
    {
        fac[0] = 1, Finv[0]=1,inv[1]=1;
        for(int i=2;i<N;i++) inv[i]=1ll * (mod-mod/i)*inv[mod%i]%mod;
        for(int i=1;i<N;i++)
        {
            fac[i]=1ll * fac[i-1]*i%mod;
            Finv[i]=1ll * Finv[i-1]*inv[i]%mod;
//            PLN(Finv[i]);
        }
    }
    int C(int n,int m)
    {
        if(n<0||m<0||m>n) return 0;
        if(n == m || m == 0) return 1;
        return 1ll *  fac[n] * Finv[m] %mod * Finv[n-m] %mod;
    }
    int A(int n,int m)
    {
        return 1ll * fac[n] * Finv[n-m] % mod;
    }
}O_O;
bool vis[N];
int main()
{
//    __IN;__OUT;
    O_O.init();
    int ans = 0,l,r,cnt = 0;
    scanf("%d %d",&l,&r);
    FOR(i,l,r)
        if(!vis[i])
        {
            cnt++;
            for(int j=i+i;j<=r;j+=i)vis[j] = 1;
        }
    int n = r-l+1;
    FOR(i,cnt,n) ans = (ans + 1ll * i * cnt % mod * O_O.A(i-1,cnt-1) % mod * fac[n-cnt]) % mod;
    printf("%d",ans);
    return 0;
}