P4562 [JXOI2018]遊戲 推式子

要求 \(O(n)\) ，明顯不能直接枚舉，我們考慮用期望來做這個事情，因為期望可以看做是一種平均值。

我們稱不能夠被 \([l,r]\) 中的任何一個數整除的數稱為僞素數。

考慮對于一個順序 \(p\) ，\(t(p)\) 的值應該是最靠右的僞素數。這個結論不難證明。

是以我們要算的就是僞素數的位置期望乘上總方案數，也就是 \(n!\)

是以答案為：

\[n!\times (\sum\limits_{i=k}^n\frac{i\times \binom{i-1}{k-1}}{\binom{n}{k}})\\ =\sum\limits_{i=k}^ni\times n!\times \frac{(i-1)!}{(k-1)!(i-k)!}\times \frac{k!(n-k)!}{n!}\\ =\sum\limits_{i=k}^n\frac{i!}{k!(i-k)!}\times k\times (n-k)!\times k!\\ =k\times (n-k)!\times k!\times \sum\limits_{i=k}^n\binom{i}{k}\\ =k\times (n-k)!\times k!\times \binom{n+1}{k+1}\\ =k\times (n-k)!\times k!\times \frac{(n+1)!}{(n-k)!(k+1)!}\\ =\frac{k}{k+1}\times (n+1)! \]

#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\n",ans);
    return 0;
}