给定 $[l, r]$ 区间,对于区间内所有数的一个顺序,每次取出最前面的数并将其倍数划去,当所有区间的数都被划去时停止。求所有排列中,取出的数的个数之和。
$1\leq l\leq r\leq 10^7$,答案对 $10^9+7$ 取模。
"> 给定 $[l, r]$ 区间,对于区间内所有数的一个顺序,每次取出最前面的数并将其倍数划去,当所有区间的数都被划去时停止。求所有排列中,取出的数的个数之和。
$1\leq l\leq r\leq 10^7$,答案对 $10^9+7$ 取模。
"> Luogu - P4562 - [JXOI2018]游戏 - TonyYin - Blog
Luogu – P4562 – [JXOI2018]游戏

题意

给定 $[l, r]$ 区间,对于区间内所有数的一个顺序,每次取出最前面的数并将其倍数划去,当所有区间的数都被划去时停止。求所有排列中,取出的数的个数之和。

$1\leq l\leq r\leq 10^7$,答案对 $10^9+7$ 取模。

分析

对于每个顺序,有一些特殊的数必须被取,并且全部取完这些之后就不用再取了。

可以发现这些数的特征是:除了自己外,没有因子在 $[l, r]$ 内。由于没有因子在 $[l, r]$ 内,这些数不可能被提前划去。

回到题目对 $t(p)$ 的定义,可以知道对于任意排列 $p$,$t(p)$ 的数值,就是顺序中最后一个这样特殊的数的位置

比如:在对于 $[3, 8]$ 的顺序 $5, 3, 8, 6, 7, 4$ 当中,$4$ 就是其中的一个关键数。$4$ 不能被区间内的其他数提前划掉,这个顺序的 $t(p)=6$.

先考虑如何快速找出这些数。

我们可以用线性筛法,预处理出每个数的最小值因子 $\min_x$,这样用 $\dfrac{x}{\min_x}$ 就可以求出 $x$ 的最大因子 $\max_x$. 如果 $\max_x < l$,那么 $x$ 就是特殊的数。

此时我们已经知道了特殊的数有哪些,考虑如何直接算出答案。

设一共有 $s$ 个特殊的数,则答案为:

$$
\sum_{i=s}^{n}{i\times \dbinom{i-1}{s – 1}\times (s-1)!\times s\times (n-s)!}
$$

可以理解为,枚举最后一个关键数的位置,统计其贡献:若有 $x$ 个排列使得最后一个关键数的位置为 $i$,那么其对答案的贡献为 $i\times x$.

现在要求的就是这个 $x$.

首先,我们要在 $i$ 这个位置放一个关键数,这个数可以在关键数中随便取,方案数为 $s$.

$\tbinom{i-1}{s-1}$ 是说,在前 $i-1$ 个位置放进去 $s-1$ 个关键数,这 $s-1$ 个数的顺序随意,所以还要乘上一个 $(s-1)!$.

对剩下没放的 $n-s$ 个数,可以在所有空余的地方随便放,方案数为 $(n-s)!$.

于是我们得到上面的答案,预处理组合数后,循环一次求解即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e7 + 10, mod = 1e9 + 7;
int l, r;
bool is_prime[MAXN];
int min_div[MAXN], prime[MAXN], cnt = 0;//min_div[x] 为x的最小非1因子
int fac[MAXN], inv_fac[MAXN];
inline int power(int x, int k, int mod) { //快速幂
	int res = 1;
	while(k) {
		if(k & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		k >>= 1;
	}
	return res;
}
inline void init() { //预处理组合数(阶乘 & 阶乘的逆元)
	fac[0] = 1;
	for(int i = 1; i <= r; i++) {
		fac[i] = fac[i - 1] * i % mod;
	}
	inv_fac[r] = power(fac[r], mod - 2, mod);
	for(int i = r - 1; i >= 0; i--) {
		inv_fac[i] = inv_fac[i + 1] * (i + 1) % mod;
	}
}
inline int C(int n, int m) { //求组合数,C(n, m) = C_n^m
	return fac[n] * inv_fac[m] % mod * inv_fac[n - m] % mod;
}
signed main() {
	scanf("%lld%lld", &l, &r);
	int n = r - l + 1;
	init();
	if(l == 1) { //这里需要特判,因为下面的因子并不包括1,对于l=1的情况容易直接得出答案
		cout << fac[n] * (n + 1) % mod * 500000004 % mod;
		return 0;
	}
	for(int i = 2; i <= r; i++) is_prime[i] = 1;
	for(int i = 2; i <= r; i++) { //线性筛,求每个数的最小因子
		if(is_prime[i]) {
			prime[++cnt] = i; min_div[i] = i;
		}
		for(int j = 1; j <= cnt && i * prime[j] <= r; j++) {
			is_prime[i * prime[j]] = false;
			min_div[i * prime[j]] = prime[j];
			if(i % prime[j] == 0) break;
		}
	}
	int sum = 0, ans = 0;
	for(int i = l; i <= r; i++) sum += (i / min_div[i] < l); //求特殊数的个数
	for(int i = sum; i <= n; i++) { //求解答案
		ans += i * C(i - 1, sum - 1) % mod * fac[sum] % mod * fac[n - sum] % mod;
		ans %= mod;
	}
	cout << ans % mod << endl;
	return 0;
}

 

 

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇