[JXOI2018]游戏（组合数学）

题目链接

题解

我们称当一个数 $k$ 除了它本身的因数不在这个序列里的时候， $k$ 为特异数。

我们发现，当且仅当我们选完最后一个特异数的时候，整个数列被选完。

于是枚举每个位置为最后一个特异数的位置计算期望，答案为：

$encoding="application/x-tex">ans=\sum_{i=1}^{n} i\times sum\times C_{n-sum}^{n-i}\times (n-i)! \times (i-1)!</annotation></semantics></math>$

其中 $i$ 为选花费， $s u m$ 为特异数的个数

求逆元的时候要线性推，要不然会T

代码

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
const int MAXN=10000010;
typedef long long ll;
ll l,r;
ll sum,ans;
bool book[MAXN];
ll fact[MAXN];
ll inv[MAXN];

ll qpow(ll a,ll b,ll p){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
void pre(){
    for(int i=l;i<=r;i++){
        if(book[i])continue;
        sum++;
        for(int j=i;j<=r;j+=i){
            book[j]=1;
        }
    }
    fact[0]=1;
    for(int i=1;i<=r;i++){
        fact[i]=fact[i-1]*i%MOD;
    }
    inv[r]=qpow(fact[r],MOD-2,MOD);
    for(int i=r-1;i>=0;i--){
        inv[i]=inv[i+1]*(i+1)%MOD;
    }
}


ll C(ll n,ll m){
    if(n<m)return 0;
    return fact[n]*inv[n-m]%MOD*inv[m]%MOD;
}

int main(){
    cin>>l>>r;
    pre();
    ll n=r-l+1;
    for(int i=1;i<=n;i++){
        ans=(ans+i*C(n-sum,n-i)%MOD*fact[n-i]%MOD*fact[i-1]%MOD*sum%MOD)%MOD;
    }
    cout<<ans<<endl;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int MOD=1e9+7;

const int MAXN=10000010;

typedef long long ll;

ll l,r;

ll sum,ans;

bool book[MAXN];

ll fact[MAXN];

ll inv[MAXN];

ll qpow(ll a,ll b,ll p){

ll ans=1;

while(b){

if(b&1)ans=ans*a%p;

a=a*a%p;

b>>=1;

}

return ans;

}

void pre(){

for(int i=l;i<=r;i++){

if(book[i])continue;

sum++;

for(int j=i;j<=r;j+=i){

book[j]=1;

}

fact[0]=1;

for(int i=1;i<=r;i++){

fact[i]=fact[i-1]*i%MOD;

}

inv[r]=qpow(fact[r],MOD-2,MOD);

for(int i=r-1;i>=0;i--){

inv[i]=inv[i+1]*(i+1)%MOD;

}

ll C(ll n,ll m){

if(n<m)return 0;

return fact[n]*inv[n-m]%MOD*inv[m]%MOD;

}

int main(){

cin>>l>>r;

pre();

ll n=r-l+1;

for(int i=1;i<=n;i++){

ans=(ans+i*C(n-sum,n-i)%MOD*fact[n-i]%MOD*fact[i-1]%MOD*sum%MOD)%MOD;

}

cout<<ans<<endl;

return 0;

}

发送评论编辑评论

题解

代码

分享到微信

发送评论 编辑评论

发送评论编辑评论