[JXOI2018]游戏

题目

思路

解法1

发现两个数\(x,y\)的关系只有两种，分别是：

1. 选择\(x\)就可以完全包含选择\(y\)，如选了2就完全包含选择6的作用

2. 只要没有包含关系，那么两个数就无法替代对方

所以有些数必须选，除此之外的数无关紧要，只需要求出必须选的数即可，设它为\(m\)，可以用欧拉筛或者埃氏筛得到

对于任何一个排列，我们只关心这m个数中的最后一个数的位置（因为只有它影响这个排列的答案），其它的数只是排列方式不同，用排列算种数即可

于是得到式子\[ans=(n-m)! \times \sum_{i=m-1}^{n-1}{A_i^{m-1}m(i+1)}\]

Code

#include<bits/stdc++.h>
#define N 10000005
using namespace std;
typedef long long ll;
const ll mod = 1000000007; 
int l,r,n,m;
int p[N],ma[N],cnt;
bool isnotp[N];
ll jc[N],inv[N];

ll quickpow(ll a,ll b)
{
    ll ret=1;
    while(b)
    {
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}
void init(int maxn)
{
    jc[0]=1;
    for(int i=1;i<=maxn;++i) jc[i]=jc[i-1]*i%mod;
    inv[maxn]=quickpow(jc[maxn],mod-2);
    for(int i=maxn-1;i>=0;--i) inv[i]=inv[i+1]*(i+1)%mod;
    
    isnotp[1]=1;
    for(int i=2;i<=maxn;++i)
    {
        if(!isnotp[i]) p[++cnt]=i,ma[i]=1;
        for(int j=1;j<=cnt&&(ll)p[j]*i<=maxn;++j)
        {
            isnotp[p[j]*i]=1;
            ma[p[j]*i]=i;
            if(i%p[j]==0) break;
        }
    }
}
ll A(int n,int m) { return n>=m ? jc[n]*inv[n-m]%mod : 0; }

int main()
{
    cin>>l>>r;
    init(r);
    n=r-l+1;
    for(int i=l;i<=r;++i) m+=(ma[i]<l);
    ll ans=0;
    for(int i=m-1;i<=n-1;++i) ans=(ans+A(i,m-1)*m%mod*(i+1)%mod)%mod;
    cout<<(ans*jc[n-m]%mod+mod)%mod<<endl;
    return 0;
}