XIII.[JXOI2018]游戏
这题好像根本不算概率期望罢……
我们考虑\([l,r]\)中，如果删去了区间中所有不是区间中其他任何数的倍数的数，则整个区间内所有的数都会被删去；反之，假如剩下了某些不是区间中其他任何数的倍数的数，则此区间一定不会被全部删完。
于是我们考虑求出区间中上述数的个数。考虑一个数满足上述条件的充分必要条件，就是它的最大约数\(<l\)。一个数的最大约数，可以直接通过线性筛求出来，复杂度\(O(n)\)。
然后我们考虑计算答案。我们考虑最后一个满足条件的数出现在序列中第\(i\)个位置的情形（应有\(i\geq m\)）：
此时，共有
\[(i-1)!\times m\times\dbinom{n-m}{i-m}\times (n-i)!
\]
个排列满足上述条件。其中，\((i-1)!\)是枚举前\(i-1\)个位置填哪些数，\(m\)是枚举第\(i\)个位置填什么数，\(\dbinom{n-m}{i-m}\)找出哪些不满足条件的数应被填入前\(i\)个位置中，\((n-i)!\)枚举剩下位置的方案数。
组合数和阶乘可以通过\(O(n)\)预处理得到；则总复杂度\(O(n)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int l,r,n,m,pri[10010000],fac[10010000],inv[10010000],res;
void Ural(){
if(l==1){m=1;return;}
for(int i=2;i<=r;i++){
if(!pri[i])pri[++pri[0]]=i,m+=(l<=i);
for(int j=1;j<=pri[0]&&i*pri[j]<=r;j++){
pri[i*pri[j]]=true;
m+=(l<=i*pri[j]&&l>i);
if(!(i%pri[j]))break;
}
}
}
int ksm(int x,int y){
int z=1;
for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;
return z;
}
#define C(x,y) (1ll*fac[(x)]*inv[(y)]%mod*inv[(x)-(y)]%mod)
int main(){
scanf("%d%d",&l,&r),n=r-l+1;
Ural();
fac[0]=1;
for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=ksm(fac[n],mod-2);
for(int i=n-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
for(int i=m;i<=n;i++)(res+=1ll*i*m%mod*fac[i-1]%mod*C(n-m,i-m)%mod*fac[n-i]%mod)%=mod;
printf("%d\n",res);
return 0;
}