[JXOI 2018] 游戏 解题报告 (组合数+埃氏筛)

interlinkage:

https://www.luogu.org/problemnew/show/P4562

description:

solution:

• 注意到$l=1$的时候，$t(p)$就是$1$出现的位置，答案就是$1$出现的位置之和;
• 这启发我们找一些关键的数字，这些数字在$[l,r]$内不存在约数;
• 结论是$t(p)$为最后一个关键数的位置;
• 不妨反证法，假设当所有的关键数都被用掉时还有数字没有筛掉。设最后一个关键数的位置为$pos$，既然还没有全部筛完，那么在$[pos+1,n]$之间还存在数字没有被筛掉。对于其中一个没有被筛掉的数，由于它并不是关键数，那么它的某一个约数一定还没有被筛掉，那么它约数的约数也没有被筛掉...以此类推，直到一个在$[l,r]$之间没有约数的数还没有被筛掉，但我们又知道这样的数已经被用完了，假设不成立;
• 我们可以通过埃氏筛算出关键数的个数$sum$;
• 设$f_i$为$t(p)$等于$i$的排列个数，$n=r-l+1$,$f_i=sum*\dbinom{n-sum}{n-i}*(n-i)!*(i-1)!$;
• $ans=\sum_{i=sum}^{n}f_i*i$;

code:

#include<cstring> #include<cstdio> #include<iostream> #include<algorithm>
using namespace std; typedef long long ll; const int N=1e7+15; const int mo=1e9+7; int l,r,sum,n; bool vis[N]; int fac[N],finv[N]; int qpow(int a,int b) { int re=1; for (;b;b>>=1,a=1ll*a*a%mo) if (b&1) re=1ll*re*a%mo; return re; } int C(int a,int b) { if (a==b||!b) return 1; return 1ll*fac[a]*finv[b]%mo*finv[a-b]%mo; } int main() { scanf("%d%d",&l,&r); n=r-l+1; fac[0]=1; for (int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mo; for (int i=l;i<=r;i++) { if (!vis[i]) { sum++; for (int j=i<<1;j<=r;j+=i) vis[j]=1; } } finv[n]=qpow(fac[n],mo-2); for (int i=n-1;i>=1;i--) finv[i]=1ll*finv[i+1]*(i+1)%mo; int ans=0; for (int i=sum;i<=n;i++) { (ans+=1ll*sum*C(n-sum,n-i)%mo*fac[n-i]%mo*fac[i-1]%mo*i%mo)%=mo; } printf("%d\n",ans); return 0; }

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄

×

选择打赏方式：

微信 QQ钱包 支付宝

打赏

打赏

打赏

多少都是心意！谢谢大家！！！