P3214 [HNOI2011] 卡农 题解

Description

给定 $n,m$，要从 $1,2,\dots,2^n-1$ 中选 $m$ 个无序的数，使得他们互不相同且异或和为 $0$，问有多少种选法。

对 $998244353$ 取模。

Solution

考虑求出有序的方案数的个数再除以 $m!$。

设 $f_i$ 表示选出 $i$ 个数的方案。

那么如果随便选前 $i-1$ 个数，那么一定有唯一的一个数使得这个数和前 $i-1$ 个数异或和为 $0$，这里的方案数就是 $A_{2^n-1}^{i-1}$。

但是有些方案数是不合法的。

首先是前 $i-1$ 个数异或和为 $0$，有 $f_{i-1}$ 种。

然后就是第 $i$ 个数出现了重复。

那么设第 $i$ 个数为 $x$，那么把所有 $i$ 个数中的两个 $x$ 丢掉，剩下的 $i-2$ 个数异或和一定为 $0$，那么这一类的方案数就是 $f_{i-2}\cdot (i-1)\cdot \left(2^n-1-\left(i-2\right)\right)$。

所以 $f_{i}=A_{2^n-1}^{i-1}-f_{i-1}-f_{i-2}\cdot (i-1)\cdot \left(2^n-1-\left(i-2\right)\right)$。

时间复杂度：$O(n+m)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e6 + 5, kMod = 1e8 + 7;

namespace Modular {
template<class T>
T qpow(T bs, T idx, T kMod) {
  bs %= kMod;
  int ret = 1;
  for (; idx; idx >>= 1, bs = 1ll * bs * bs % kMod)
    if (idx & 1)
      ret = 1ll * ret * bs % kMod;
  return ret;
}
int inv(int x, int kMod) {
  x %= kMod;
  if (!x) { std::cerr << "inv error\n"; return 0; }
  return qpow(x, kMod - 2, kMod);
}
template<class T, const T kMod>
T add(T x, T y) {
  if (x + y >= kMod) return x + y - kMod;
  else return x + y;
}

template<class T, const T kMod>
T sub(T x, T y) {
  if (x - y < 0) return x - y + kMod;
  else return x - y;
}

template<class T, const T kMod>
struct Mint {
  T x;

  Mint() { x = 0; }
  template<class _T> Mint(_T _x) { x = _x; }

  friend Mint operator +(Mint m1, Mint m2) { return Mint(Modular::add<T, kMod>(m1.x, m2.x)); }
  friend Mint operator -(Mint m1, Mint m2) { return Mint(Modular::sub<T, kMod>(m1.x, m2.x)); }
  friend Mint operator *(Mint m1, Mint m2) { return Mint(1ll * m1.x * m2.x % kMod); }
  friend Mint operator /(Mint m1, Mint m2) { return Mint(1ll * m1.x * inv(m2.x, kMod) % kMod); }
  Mint operator +=(Mint m2) { return x = Modular::add<T, kMod>(x, m2.x); }
  Mint operator -=(Mint m2) { return x = Modular::sub<T, kMod>(x, m2.x); }
  Mint operator *=(Mint m2) { return x = 1ll * x * m2.x % kMod; }
  Mint operator /=(Mint m2) { return x = 1ll * x * inv(m2.x, kMod) % kMod; }

  template<class _T> friend Mint operator +(Mint m1, _T m2) { return Mint(Modular::add<T, kMod>(m1.x, m2 % kMod)); }
  template<class _T> friend Mint operator -(Mint m1, _T m2) { return Mint(Modular::sub<T, kMod>(m1.x, m2 % kMod)); }
  template<class _T> friend Mint operator *(Mint m1, _T m2) { return Mint(1ll * m1.x * m2 % kMod); }
  template<class _T> friend Mint operator /(Mint m1, _T m2) { return Mint(1ll * m1.x * inv(m2, kMod) % kMod); }
  template<class _T> Mint operator +=(_T m2) { return x = Modular::add<T, kMod>(x, m2); }
  template<class _T> Mint operator -=(_T m2) { return x = Modular::sub<T, kMod>(x, m2); }
  template<class _T> Mint operator *=(_T m2) { return x = 1ll * x * m2 % kMod; }
  template<class _T> Mint operator /=(_T m2) { return x = 1ll * x * inv(m2, kMod) % kMod; }
  template<class _T> friend Mint operator +(_T m1, Mint m2) { return Mint(Modular::add<T, kMod>(m1 % kMod, m2.x)); }
  template<class _T> friend Mint operator -(_T m1, Mint m2) { return Mint(Modular::sub<T, kMod>(m1 % kMod, m2)); }
  template<class _T> friend Mint operator *(_T m1, Mint m2) { return Mint(1ll * m1 * m2.x % kMod); }
  template<class _T> friend Mint operator /(_T m1, Mint m2) { return Mint(1ll * m1 * inv(m2.x, kMod) % kMod); }
  friend Mint operator -(Mint &m1) { return Mint(m1.x == 0 ? (kMod - 1) : (m1.x - 1)); }
  friend Mint operator --(Mint &m1) { return m1 = Mint(m1.x == 0 ? (kMod - 1) : (m1.x - 1)); }
  friend Mint operator ++(Mint &m1) { return m1 = Mint(m1.x == (kMod - 1) ? 0 : (m1.x + 1)); }
  friend bool operator ==(Mint m1, Mint m2) { return m1.x == m2.x; }

  friend std::istream &operator >>(std::istream &is, Mint &m) {
    int x;
    is >> x;
    m = Mint(x);
    return is;
  }
  friend std::ostream &operator <<(std::ostream &os, Mint m) {
    os << m.x;
    return os;
  }
};
} // namespace Modular

using mint = Modular::Mint<int, kMod>;

int n, m;
mint pw2, f[kMaxN];

mint Fac(int n) {
  mint ret = 1;
  for (int i = 1; i <= n; ++i)
    ret *= i;
  return ret;
}

void dickdreamer() {
  std::cin >> n >> m;
  pw2 = 1;
  for (int i = 1; i <= n; ++i)
    pw2 *= 2;
  f[0] = 1;
  mint A = pw2 - 1;
  for (int i = 2; i <= m; ++i) {
    f[i] = A - f[i - 1] - f[i - 2] * (i - 1) * (pw2 - i + 1);
    A *= pw2 - i;
  }
  std::cout << f[m] / Fac(m) << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}