正題

題目鏈接:https://www.luogu.org/problemnew/show/P4562

---

題目大意

$l～r$的變化，每次訪問第$i$個那么$i$的倍數就不用訪問了。對于一個順序$s$，定義$t(s)$表示按這個順序訪問玩前$t(s)$個就都不用訪問了。求所有順序的$t(s)$之和。

---

解題思路

若$l==1$時那么只要訪問$1$就好了，所以答案是$\frac{r!?(r+1)}{2}$
若$l!=1$時我們用質數篩的方法計算有多少個是需要訪問的，定義個數為$m$，然后我們用$i$枚舉$t(s)$，首先這樣的序列有$m?C_{n?i}^{n?sum}?(i?1)!?(n?i)!$
$C_{n?i}^{n?sum}$表示后面不用選的方案數，然后$(n?i)!$將其排列，$(i?1)!$表示前面的排列順序
然后乘上一個$i$表示$t(s)$

---

$code$

#include<cstdio> #include<algorithm> #define ll long long using namespace std; const ll N=1e7+10,XJQ=1e9+7; ll l,r,fac[N],inv[N],ans,sum,n; bool v[N]; ll power(ll x,ll b){ll ans=1;while(b){if(b&1) ans=(ans*x)%XJQ;x=(x*x)%XJQ;b>>=1;}return ans; } int main() {scanf("%lld%lld",&l,&r);n=r-l+1;fac[0]=1;for(ll i=1;i<=r;i++)fac[i]=fac[i-1]*i%XJQ;inv[r]=power(fac[r],XJQ-2);for(ll i=r;i;i--)inv[i-1]=inv[i]*i%XJQ;if(l==1){printf("%lld",fac[r]*(r+1)%XJQ*power(2,XJQ-2)%XJQ);return 0;}for(ll i=l;i<=r;i++){if(v[i]) continue;sum++;for(ll j=i*2;j<=r;j+=i)v[j]=1;}for(ll i=sum;i<=n;i++)(ans+=sum*fac[n-sum]%XJQ*inv[i-sum]%XJQ*fac[i]%XJQ)%=XJQ;printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的P4562-[JXOI2018]游戏【数论,组合数学】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。