B3901 星空 [Easy Version]
wyf1202
·
·
题解
题目传送门
因此，我们只需要考虑重排后最大值与相邻位置的和是否合法。
枚举最大值所在的位置 $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)$。
```cpp
//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;
}
```
请各位大佬多多指教，如有不足请提出！