B3901 [NICA #3] 星空（Easy Version）题解

DFM_O · 2024-02-02 17:16:47 · 题解

B3901题目

解题思路

由题意易知，若序列 a 的最大值与最小值之和大于 x，则此题无解，输出 0。

因为每一个 a_i 都不重复且序列中的每个数都是 2 的整数次幂，所以在序列中任选两数，且这两个数均不是序列的最大值，则这两数之和一定不大于最大值。

因为我们已经对于无解的情况进行了特判，所以最大值一定小于 x。

即我们只需要注意最大值和与最大值相邻的数，其他数无论怎么排都小于 x。

最后求出可以与最大值相邻的数的数量，并用排列数求出答案即可。

Code

#include<bits/stdc++.h>//万能头
using namespace std;
const int p=1e9+7;
long long a[62];
long long A(long long a,long long b)//排列
{
    long long s=1;
    for(int i=a;i>=a-b+1;i--)
        s=s*i%p;
    return s;
}
int main()
{
    long long n,x,max,l=-1,m=0;
    cin>>n>>x;
    for(long long i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    max=a[n];
    for(long long i=n-1;i>=1;i--)
    {
        if(a[i]+max<=x)
        {
            l=i;
            break;
        }
    }
    if(l==-1)//对于无解的情况进行特判
    {
        cout<<0;
        return 0;
    }
    l=n-1-l;//统计可以与最大值相邻的数的数量
    m+=(n-1)*l*2%p*A(n-2,n-2)%p;
    if(l>1)
        m-=(n-2)*A(l,2)%p*A(n-3,n-3)%p;
    if(m<0) 
        m+=p;   
    m=A(n,n)-m%p;
    if(m<0) 
        m+=p;       
    cout<<m;        
    return 0;
}