题解：B3903 [NICA #3] 星空（Hard Version）

· · 题解

提供一种 O(1) 回答的方法。

如果存在一个 a_i \ge x，那么它和任意别的数相加都大于 x，答案为 0。

如果 x 在二进制下只有一位且不存在 a_i \ge x，显然任意的顺序都合法，答案为 n!。

设 B 类数为 x 在二进制下最高一位所表示的数，A 类数为与 B 类数相加大于 x 的数，C 类数为其他数。

拿样例举例，46 的二进制表示为 101110，那么二进制表示为 100000 的数，即 32，为 B 类数。16 为 A 类数，4,8 为 C 类数。

那么限制就是 B 类数只能与 C 类数相邻。

设 A 类数有 a 个，B 类数有 b 个，C 类数有 c 个。

假设已经放好了所有 C 类数，考虑把所有 B 类数放进去，现在有 c+1 个空可以插 B 类数，那么答案即为 {c+1 \choose b}。

现在考虑放 A 类数，设放完 B 类数后空的个数为 t，那么 t=c+1-b。现在要在这 t 个空中放 a 个数，一个空可以不放数，这是个经典问题（如果你不会，请看文末），答案为 {a+t-1 \choose t-1}。

根据乘法原理，相乘即可得到答案。

因为每个数互不相同，最后答案要乘上 a!\times b! \times c!。

答案为：

{c+1\choose b}\times {a+t-1\choose t-1}\times a!\times b! \times c! 
#include <bits/stdc++.h>

#define mkp make_pair
#define fi first
#define se second
#define vec vector
#define eb emplace_back

using namespace std;

#define int long long

const int mod = 1e9 + 7;

signed main() {
  int n, X;
  cin >> n >> X;
  vec<int> a(n + 3);
  int Mx = 0;
  for (int i = 1; i <= n; i++)
    cin >> a[i], Mx = max(Mx, a[i]);

  if (Mx >= X) {
    cout << "0\n";
    return 0;
  }

  vec<int> fc(n * 2 + 3), ifc(n * 2 + 3);
  fc[0] = 1;
  for (int i = 1; i <= n * 2; i++)
    fc[i] = fc[i - 1] * i % mod;
  auto ksm = [](int a, int b = mod - 2) {
    int r = 1;
    while (b) {
      (b & 1) && (r = r * a % mod);
      a = a * a % mod;
      b >>= 1;
    }
    return r;
  };
  ifc[n * 2] = ksm(fc[n * 2]);
  for (int i = n * 2 - 1; i >= 0; i--)
    ifc[i] = ifc[i + 1] * (i + 1) % mod;

  auto Cc = [&](int n, int m) -> int {
    if (n < 0 || m < 0 || n < m) return 0;
    return fc[n] * ifc[m] % mod * ifc[n - m] % mod;
  };

  if (__builtin_popcountll(X) == 1) {
    // 计算二进制下 1 的个数
    cout << fc[n] << '\n';
    return 0;
  }

  auto tmp = X, ls = 0ll;
  while (tmp - (tmp & -tmp))
    ls = tmp, tmp -= tmp & -tmp;

  ls -= tmp;

  int A = 0, B = 0, C = 0;
  for (int i = 1; i <= n; i++)
    B += (a[i] == tmp), A += (tmp > a[i] && a[i] > ls);
  C = n - A - B;

  int t = C + 1 - B;
  int ans = Cc(C + 1, B) * (A ? Cc(A + t - 1, t - 1) : 1) % mod;

  ans *= fc[C] * fc[B] % mod * fc[A] % mod;
  ans %= mod;
  cout << ans << '\n';
}

有 m 个小球，要放到 n 个盒子中，盒子可以为空，求方案数。

设第 i 个盒子中有 x_i 个球，有 \sum\limits_{i=1}^n x_i=m，其中 x_i\ge 0。

我们不太会做 x_i\ge 0，但我们会做 x_i\ge 1。把上面变一下，有 \sum\limits_{i=1}^n(x_i+1)=m+n，其中 x_i+1\ge 1。相当于一共有 n+m 个球放到 n 个盒子中，盒子不能为空的方案数。n+m 个球两两之间有 n+m-1 个空，从中选 n-1 个空可以把它们分成 n 份，相当于放到 n 个盒子中。

得到答案：

{n+m-1\choose n-1}