P4562 [JXOI2018]游戏 推式子

链接

要求 (O(n)) ，明显不能直接枚举，我们考虑用期望来做这个事情，因为期望可以看做是一种平均值。

我们称不能够被 ([l,r]) 中的任何一个数整除的数称为伪素数。

考虑对于一个顺序 (p) ，(t(p)) 的值应该是最靠右的伪素数。这个结论不难证明。

所以我们要算的就是伪素数的位置期望乘上总方案数，也就是 (n!)

所以答案为：

[n! imes (sumlimits_{i=k}^nfrac{i imes inom{i-1}{k-1}}{inom{n}{k}})\ =sumlimits_{i=k}^ni imes n! imes frac{(i-1)!}{(k-1)!(i-k)!} imes frac{k!(n-k)!}{n!}\ =sumlimits_{i=k}^nfrac{i!}{k!(i-k)!} imes k imes (n-k)! imes k!\ =k imes (n-k)! imes k! imes sumlimits_{i=k}^ninom{i}{k}\ =k imes (n-k)! imes k! imes inom{n+1}{k+1}\ =k imes (n-k)! imes k! imes frac{(n+1)!}{(n-k)!(k+1)!}\ =frac{k}{k+1} imes (n+1)! ]

其中证明第 (5) 行用到了朱世杰恒等式。

代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 10000100
#define M number
using namespace std;

const int INF=0x3f3f3f3f;
const ll mod=1e9+7;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int l,r,cnt;
bool notPrime[N];

int main(){
    read(l);read(r);
    for(int i=l;i<=r;i++){
        if(!notPrime[i]){
            cnt++;
            for(int j=i<<1;j<=r;j+=i) notPrime[j]=1;
        }
    }
    ll ans=cnt;
    for(int i=1;i<=r-l+2;i++){
        if(i!=cnt+1) (ans*=i)%=mod;
    }
    printf("%lld
",ans);
    return 0;
}