Как через bitmask DP посчитать число способов разбить n элементов на пары (идеальное паросочетание перебором)?

Да, классический приём — ДП по маске свободных/занятых элементов. dp[mask] = число способов разбить на пары множество людей, заданное mask (бит = «человек ещё свободен» или «занят» — оба варианта работают, важно зафиксировать смысл).

Ключ к корректности и скорости: чтобы не считать одно разбиение многократно, всегда берём первого свободного человека и перебираем ему пару. Тогда каждое разбиение строится единственным способом.

int n;
bool can[20][20];
vector<long long> dp(1 << n, 0);
dp[(1 << n) - 1] = 1; // все свободны

for (int mask = (1 << n) - 1; mask > 0; --mask) {
  if (dp[mask] == 0) continue;
  int i = __builtin_ctz(mask);      // первый свободный (младший бит)
  for (int j = i + 1; j < n; ++j)
    if ((mask & (1 << j)) && can[i][j]) {
      int nmask = mask ^ (1 << i) ^ (1 << j);
      dp[nmask] += dp[mask];
    }
}
// ответ — dp[0] (никого свободного не осталось)
long long ans = dp[0];

Сложность: $2^n$ масок, на каждой перебор $O(n)$ → $O(2^n \cdot n)$ времени, $O(2^n)$ памяти. Для $n=20$ это $\approx 2 \cdot 10^7$. Число способов растёт быстро — long long или счёт по модулю обязателен.