自动搬运

查看原文

来自洛谷，原作者为

	GTAH2333 **

搬运于2025-08-24 21:15:48，当前版本为作者最后更新于2024-04-14 21:15:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

提供一种支持多次询问的方法。

观察题目，发现可以一定可以将序列 $x$ 中的元素分成四类：黑球、灰球、白球和不可存在球。其中黑球是和灰球或黑球的数相加都大于 $x$ 的数，灰球是只与黑球相加大于 $x$ 的数，白球则与任何数相加都小于等于 $x$ ， 而不可存在球则是自身便大于等于 $x$ 的数。

可以这样分类的正确性显然可以证明：首先，题目要求 $a_i$ 一定是二的整数次幂，则可以将等于 $x$ 的二进制最高位的数作为黑球，然后将与黑球相加大于 $x$ 且不等于黑球的作为灰球，余下作白球。由于二的整数次幂的要求，白球一定小于等于灰球的一半，灰球一定小于等于黑球的一半，而黑球一定小于等于 $x$ ，则可以满足要求。若序列中有一个数大于等于 $x$ ，显然无解，因为无论是什么数排列在它旁边都不符合要求，特判设有即可。

现在我们将这个问题转化为一个排列问题。可设黑球个数为 $k_1$ ，灰球个数为 $k_2$ ，白球个数为 $k_3$ ，且要求黑黑不相邻，可得出如下公式：

$$A_{k_3}^{k_3}\times A_{k_3+1}^{k_1}\times \prod \limits ^{k_3+k_2-k_1}_{i=k_3-k_1+1} i $$

公式的意义：将白球有序排列后，将 $k_1$ 黑球放入 $k_3+1$ 个空并且两个球不在同一个空，在剩下的 $k_3-k_1+1$ 个空中依次放入灰球，而每放入一个灰球，空的个数就会加一，所以是连乘。

再特判一些特殊情况，即可正确求出答案。

code：

#include<iostream>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
inline int qpow(int a,int b) {
	int res = 1;
	while(b) {
		if(b&1) res = (1ll*a*res)%mod;
		a = (1ll*a*a)%mod;
		b>>=1;
	} 
	return res;
}
int n, k1, k2, k3;
int jc[N] = {1,1}, inv[N] = {1,1};
unsigned long long x1, val, x, a[N];
int main() {
	n = read(), x = readULL(), x1 = x>>1;
	for(int i=1;i<=n;++i) {
		a[i] = readULL(), jc[i+1] = (1ll * (i+1) * jc[i]) % mod;
		if(a[i] > x) { cout<<0; return 0; }
		else if(a[i] > x1) ++k1, val = a[i];
	}
	inv[n+1] = qpow(jc[n+1], mod-2), x -= val;
	for(int i=n;i>=1;--i) {
		inv[i] = 1ll * inv[i+1] * (i+1) % mod;
		if(a[i] > x && a[i] != val) ++k2;
		else if(a[i] <= x) ++k3;
	}
	if(k1>k3+1) cout << 0;
	else if(k2 == 0) cout << 1ll * jc[k3] * jc[k3+1] % mod * inv[k3+1-k1] % mod;
	else cout << 1ll * jc[k3] * jc[k3+1] % mod * inv[k3+1-k1] % mod * jc[k3-k1+k2] % mod * inv[k3-k1] % mod;
	return 0;
}