[JXOI2018]游戏 传送门
题目背景
九条可怜是一个富有的女孩子。
题目描述
她长大以后创业了，开了一个公司。 但是管理公司是一个很累人的活，员工们经常背着可怜偷懒，可怜需要时不时对办公室进行检查。 可怜公司有 \(n\) 个办公室，办公室编号是 \(l\) 到 \(l+n-1\) ，可怜会事先制定一个顺序，按照这个顺序依次检查办公室。一开始的时候，所有办公室的员工都在偷懒，当她检查完编号是 \(i\) 的办公室时候，这个办公室的员工会认真工作，并且这个办公室的员工通知所有办公室编号是 \(i\) 的倍数的办公室，通知他们老板来了，让他们认真工作。因此，可怜检查完第 \(i\) 个办公室的时候，所有编号是 \(i\) 的倍数(包括 \(i\) )的办公室的员工会认真工作。 可怜发现了员工们通风报信的行为，她发现，对于每种不同的顺序 \(p\) ，都存在一个最小的 \(t(p)\) ，使得可怜按照这个顺序检查完前 \(t(p)\) 个办公室之后，所有的办公室都会开始认真工作。她把这个 \(t(p)\) 定义为 \(p\) 的检查时间。 可怜想知道所有 \(t(p)\) 的和。 但是这个结果可能很大，她想知道和对 \(10^9+7\) 取模后的结果。
输入输出格式
输入格式
第一行输入两个整数 \(l,r\) 表示编号范围，题目中的 \(n\) 就是 \(r-l+1\) 。
输出格式
一个整数，表示所有 \(t(p)\) 的和。
输入输出样例
输入样例
2 4
输出样例
16
solution
之前我就想到\(cnt\)个了
\(cnt\)最少需要的个数
但是我题意理解错了，我以为ta就是下标耶。。
结果是数，ta不是说的下标都嘛。。
然后后面就比较好想了
\[ans=\sum^{n}_{i=cnt}i×(i-1)!×cnt×A_{n-cnt}^{n-i} \]就是遍历\(i=t(p)\)再乘上可能的方案数
由于\(t(p)\)是最后的，所以第\(t(p)\)个必须是\(cnt\)个关键字之一，方案数\(cnt\)
剩下的\(i-1\)个数排列为\((i-1)!\)
剩下后面的数排列\(A_{n-cnt}^{n-i}\)
总的方案数就是\((i-1)!×cnt×A_{n-cnt}^{n-i}\)
CODE
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll p=1e9+7,N=1e7+2;
ll l,r,cnt,vis[N],ans,n,fac[N],inv[N];
ll qpow(ll a,ll b){
ll ans=1;
while(b){
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
ll A(ll n,ll m){
return fac[n]*inv[n-m]%p;
}
int main(){
scanf("%lld%lld",&l,&r);
for(ll i=l;i<=r;i++){
if(!vis[i]){
cnt++;
for(ll j=i;j<=r;j+=i){
vis[j]=1;
}
}
}
n=r-l+1;
fac[0]=1;
for(ll i=1;i<=r;i++){
fac[i]=fac[i-1]*i%p;
}
inv[r]=qpow(fac[r],p-2);
for(ll i=r-1;i>=0;i--){
inv[i]=inv[i+1]*(i+1)%p;
}
for(ll i=cnt;i<=n;i++){
ans+=i%p*fac[i-1]%p*cnt%p*A(n-cnt,n-i)%p;
}
printf("%lld",ans%p);
return 0;
}
完结撒花❀
★,°:.☆(￣▽￣)/$:.°★ 。
标签：cnt,办公室,ll,JXOI2018,可怜,解题,ans,inv,游戏 From： https://www.cnblogs.com/Aurora1217/p/16589416.html