[JXOI2018] 游戏

[JXOI2018] 游戏 - 组合数学

Description

给定一个区间 [l,r]，每次选第一个数，把它和它后面所有它的倍数去掉，直到序列为空，操作的次数称为这个序列的代价。求对给定序列的所有排列的代价之和。

Solution

显然对于区间内的所有数，我们可以给出这些数的一个拓扑图，那么入度为零的点的个数就是必须要选的点，其它的点在必须要选的点选完以后都不用选了，因此我们只需要考虑这些必须要选的数即可

先考虑怎样找出这些数：类似筛质数的过程

计算过程中，我们显然要考虑排在最右边的必选数的位置，我们枚举这个位置 (i)，同时设必选数的数目为 sum，考虑最后一个必选数是哪一个，这样有 (sum) 种取法，从 (n-sum) 个自由数中选出 (n-i) 个放在后面并任意排列，剩下的与必选数混在一起排列放在前面，有 ((i-1)!) 种排法，因此方案数为 (sum cdot C(n-sum, n-i) cdot (n-i)! cdot (i-1)!)

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e7 + 5;
const int mod = 1e9 + 7;

int qpow(int p, int q)
{
    return (q & 1 ? p : 1) * (q ? qpow(p * p % mod, q / 2) : 1) % mod;
}

int inv(int p)
{
    return qpow(p, mod - 2);
}

int fac[N], ifac[N];

int ncr(int n, int k)
{
    return fac[n] * ifac[n - k] % mod * ifac[k] % mod;
}

void fac_presolve()
{
    fac[0] = ifac[0] = 1;
    for (int i = 1; i < min(N, mod); i++)
        fac[i] = fac[i - 1] * i % mod;
    ifac[min(N, mod) - 1] = inv(fac[min(N, mod) - 1]);
    for (int i = min(N, mod) - 2; i; i--)
        ifac[i] = ifac[i + 1] * (i + 1) % mod;
}

signed main()
{
    ios::sync_with_stdio(false);

    int l, r;
    cin >> l >> r;

    fac_presolve();

    int sum = 0;
    vector<int> v(N + 2);
    for (int i = l; i <= r; i++)
    {
        if (v[i] == 0)
        {
            ++sum;
            for (int j = i + i; j <= r; j += i)
                v[j] = 1;
        }
    }

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

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

    cout << ans << endl;
}