[NICA #3] 星空（Easy Version）(Starry Sky Easy) 题解

思路分析

将互不相同的 $2$ 的幂升序排列为 $a_1 < a_2 < \dots < a_n$。利用 $2$ 的幂的性质：除最大值 $a_n$ 外的任意两数之和满足 $a_u + a_v \le a_{n-2} + a_{n-1} < a_n$！

• 若 $a_n > x$，由于 $n \ge 2$，$a_n$ 必有相邻元素，和必 $> x$，答案为 $0$；
• 若 $a_n \le x$，则除 $a_n$ 以外的任意两个元素相邻都必定合法（$\le x$）！唯一需要满足的约束是「与最大值 $a_n$ 相邻的元素必须属于集合 $S = \{j < n : a_n + a_j \le x\}$」。设 $s = |S|$：
  • $a_n$ 放在首尾两端（$2$ 个位置）：有 $1$ 个邻居选自 $S$，其余 $n - 2$ 个元素任意排，共 $2s(n - 2)!$ 种；
  • $a_n$ 放在中间（$n - 2$ 个位置）：左右 $2$ 个邻居有序选自 $S$，其余 $n - 3$ 个元素任意排，共 $(n - 2)s(s - 1)(n - 3)! = s(s - 1)(n - 2)!$ 种。 两者相加化简得总方案数为 $s(s + 1)(n - 2)! \bmod (10^9 + 7)$。时间复杂度 $O(n \log n)$。

参考代码

#include <algorithm>
#include <iostream>
using namespace std;

const long long MOD = 1000000007LL;
unsigned long long a[70];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    unsigned long long x;
    if (!(cin >> n >> x)) return 0;
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n);

    long long s = 0;
    for (int i = 0; i < n - 1; ++i)
    {
        if (a[n - 1] + a[i] <= x) ++s;
    }
    long long fact = 1;
    for (int i = 1; i <= n - 2; ++i) fact = (fact * i) % MOD;
    long long ans = s * (s + 1) % MOD * fact % MOD;
    cout << ans << "\n";
    return 0;
}