【洛谷-P4562】[JXOI2018]游戏 • TonyYin's Blog

题意#

给定 $[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;
}

cpp