自动搬运

查看原文

来自洛谷，原作者为

	wyf1202 也许前方的路还很长，而我仍旧迷茫

搬运于2025-08-24 21:15:47，当前版本为作者最后更新于2023-12-10 10:22:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

$a$ 序列里每个元素都是 $2$ 的整数次幂，从而 $2$ 个不等于最大值的元素相加一定不大于最大值。

因此，我们只需要考虑重排后最大值与相邻位置的和是否合法。

枚举最大值所在的位置 $i$，枚举与之相邻的元素对应着数组里哪两个元素。

分析之后得到有两种情况：$1<i<n$ 和 $i=1$ 或 $i=n$。

在 $i=1$ 或 $i=n$ 时，只有当 $a_j+a_{max}\le x$ 时合法。

如果合法，那么剩下的 $n-2$ 个位置可以随意地填充剩下来的元素，共有 $(n-2)!$ 种方案。

$1<i<n$，此时与最大值相邻的有两个位置。分别枚举这个位置填放了 $a_j$ 和 $a_k(≠a_{max})$。

这个数只有当 $a_j+a_{max}\le x$ 且 $a_k+a_{max}\le x$ 时合法。

如果合法，那么剩下的 $n-3$ 个位置可以随意地填充剩下来的元素，共有 $(n-3)!$ 种方案。

这道题的数据范围很小，因此无论怎么写，都能通过本题，复杂度 $O(n)$。

//j[i]表示i的阶乘
//a[i]表示数组里的数
const int mod=1e9+7;
long long n,x,mx,sum,ans,a[100005],j[100005];
int main(){
	cin>>n>>x;
	for(int i=1;i<=n;++i)cin>>a[i];
	for(int i=1;i<=n;++i)if(a[i]>mx)mx=a[i];
	for(int i=1;i<=n;++i)
		if(a[i]!=mx&&a[i]+mx<=x)sum++;
	j[1]=1;
	for(int i=2;i<=n;++i)j[i]=(j[i-1]*i)%mod;
	for(int i=1;i<=n;++i){
		if(i==1||i==n)ans=(ans+sum*j[n-2])%mod;
		else ans=(ans+sum*(sum-1)*j[n-3])%mod;
	} cout<<ans;	return 0;
}

请各位大佬多多指教，如有不足请提出！