[JXOI 2018] 游戏 解题报告 (组合数+埃氏筛)

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N=1e7+15;
const int mo=1e9+7;
int l,r,sum,n;
bool vis[N];
int fac[N],finv[N];
int qpow(int a,int b)
{
    int re=1;
    for (;b;b>>=1,a=1ll*a*a%mo) if (b&1) re=1ll*re*a%mo;
    return re;
}
int C(int a,int b)
{
    if (a==b||!b) return 1;
    return 1ll*fac[a]*finv[b]%mo*finv[a-b]%mo;
}
int main()
{
    scanf("%d%d",&l,&r);
    n=r-l+1;
    fac[0]=1;
    for (int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mo;
    for (int i=l;i<=r;i++)
    {
        if (!vis[i])
        {
            sum++;
            for (int j=i<<1;j<=r;j+=i) vis[j]=1;
        }
    }
    finv[n]=qpow(fac[n],mo-2);
    for (int i=n-1;i>=1;i--) finv[i]=1ll*finv[i+1]*(i+1)%mo;
    int ans=0;
    for (int i=sum;i<=n;i++)
    {
        (ans+=1ll*sum*C(n-sum,n-i)%mo*fac[n-i]%mo*fac[i-1]%mo*i%mo)%=mo;
    }
    printf("%d\n",ans);
    return 0;
}