P4562 [JXOJ2018]游戏

题目描述

她长大以后创业了，开了一个公司。但是管理公司是一个很累人的活，员工们经常背着可怜偷懒，可怜需要时不时对办公室进行检查。

可怜公司有 n 个办公室，办公室编号是 l 到 l+n−1 ，可怜会事先制定一个顺序，按照这个顺序依次检查办公室。一开始的时候，所有办公室的员工都在偷懒，当她检查完编号是 i 的办公室时候，这个办公室的员工会认真工作，并且这个办公室的员工通知所有办公室编号是 i 的倍数的办公室，通知他们老板来了，让他们认真工作。因此，可怜检查完第ii 个办公室的时候，所有编号是 i 的倍数(包括 i )的办公室的员工会认真工作。

可怜发现了员工们通风报信的行为，她发现，对于每种不同的顺序 p ，都存在一个最小的 t(p) ，使得可怜按照这个顺序检查完前 t(p) 个办公室之后，所有的办公室都会开始认真工作。她把这个 t(p) 定义为 p的检查时间。

可怜想知道所有 t(p)的和。

但是这个结果可能很大，她想知道和对 109+7 取模后的结果。

输入格式

第一行输入两个整数 l,r 表示编号范围，题目中的 n就是 r−l+1 。

输出格式

一个整数，表示期望进行的轮数。

输入

2 4

输出

16

解释一下题意

个人觉得很有必要。。。

在区间\([l , r]\) 间选择若干个数，选完一个数之后，他及他的倍数都会被覆盖，求所有的方案

要选多少个数才能选完的和

首先，发现有一些数是必须选的这些数的没有除他自己以外的因子，所以必须选，设有sum个，

则选 i 个数结束的方案为

\(\huge f[i] = sum * C_{n - sum}^{n - i} * (n - i)! * (i - 1)!\)

因为在第i个位置结束，那么最后一个一定是必须选的数之一，这个数有 sum 种可能

\(\huge C_{n - sum}^{n - i}\) 是不选的数，乘上\(\huge (n - i)!\) 就是不选的部分的方案， \((i - 1)!\) 就是选的那部分除了最后一个数的方案

#include<iostream>

#include<cstdio>

using namespace std;

const int N = 1e7+10;

const int mod = 1e9+7;

int vis[N] , fac[N] , inv[N] , f[N];

int ksm(int a , int k)

{

	int ans = 1;

	for( ; k ; k >>= 1 , a = 1LL * a * a % mod)

		if(k & 1) ans = 1LL * ans * a % mod;

	return ans;

}

void Init(int maxn)

{

	fac[0] = inv[0] = 1;

	for(int i = 1 ; i <= maxn ; ++i) fac[i] = 1LL * i * fac[i-1] % mod;

	inv[maxn] = ksm(fac[maxn] , mod - 2);

	for(int i = maxn - 1 ; i >= 1 ; --i) inv[i] = 1LL * inv[i+1] * (i+1) % mod;

	return ;

}

int C(int n , int m) { if(n < m) return 0; else return 1LL * fac[n] * inv[m] % mod * inv[n-m] % mod; }

int main()

{

	int l , r;

	register int i , j , sum = 0 , n , ans;

	cin >> l >> r;

	Init(r);

	for(i = l ; i <= r ; ++i)

	{

		if(!vis[i])

		{

			sum++;

			for(j = i << 1 ; j <= r ; j += i)

				vis[j] = 1;

		}

	}

	n = r - l + 1;

	for(i = sum ; i <= n ; ++i)

		f[i] = 1LL * sum * C(n - sum , n - i) % mod * fac[n - i] % mod * fac[i - 1] % mod;

	ans = 0;

	for(i = sum ; i <= r - l + 1 ; ++i) ans = (1LL * ans + 1LL * f[i] * i % mod) % mod;

	cout << ans << endl;

	return 0;

}

巴特西

P4562 [JXOJ2018]游戏

题目描述

输入格式

输出格式

最新文章

热门文章