seq/domino_standard_tableaux.hpp

• View this file on GitHub
• Last update: 2022-12-07 02:54:40+09:00
• Include: #include "seq/domino_standard_tableaux.hpp"

Depends on

• seq/hook_length_formula.hpp

Verified with

• test/yukicoder/2149.test.cpp

Code

#include "seq/hook_length_formula.hpp"

template <typename mint>
mint domino_standard_tableaux(vc<int> A) {
  int N = len(A);
  if (N == 0) return mint(1);
  FOR(i, N - 1) assert(A[i] >= A[i + 1]);
  int x = 0;
  FOR(i, N) {
    if (A[i] % 2 == 1) { x += (i % 2 == 0 ? 1 : -1); }
  }
  if (x != 0) return 0;
  FOR(i, N) A[i] += N - 1 - i;
  int ev = 0, od = 0;
  vc<int> P, Q;
  FOR_R(i, N) {
    if (A[i] % 2 == 0) { P.eb(A[i] / 2 - ev), ++ev; }
    if (A[i] % 2 == 1) { Q.eb(A[i] / 2 - od), ++od; }
  }
  reverse(all(P)), reverse(all(Q));
  int b = SUM<int>(P), c = SUM<int>(Q);
  return C<mint>(b + c, b) * hook_length_formula<mint>(P)
         * hook_length_formula<mint>(Q);
}

#line 2 "seq/hook_length_formula.hpp"

template <typename mint>
mint hook_length_formula(vc<int> A) {
  if (len(A) == 0) return 1;
  int H = len(A), W = A[0];
  FOR(i, H - 1) assert(A[i] >= A[i + 1]);
  vc<int> B(W);
  reverse(all(A));
  mint ANS = fact<mint>(SUM<int>(A));
  for (auto&& a: A) {
    FOR(j, a) { ANS *= inv<mint>(B[j] + a - j), ++B[j]; }
  }
  return ANS;
}
#line 2 "seq/domino_standard_tableaux.hpp"

template <typename mint>
mint domino_standard_tableaux(vc<int> A) {
  int N = len(A);
  if (N == 0) return mint(1);
  FOR(i, N - 1) assert(A[i] >= A[i + 1]);
  int x = 0;
  FOR(i, N) {
    if (A[i] % 2 == 1) { x += (i % 2 == 0 ? 1 : -1); }
  }
  if (x != 0) return 0;
  FOR(i, N) A[i] += N - 1 - i;
  int ev = 0, od = 0;
  vc<int> P, Q;
  FOR_R(i, N) {
    if (A[i] % 2 == 0) { P.eb(A[i] / 2 - ev), ++ev; }
    if (A[i] % 2 == 1) { Q.eb(A[i] / 2 - od), ++od; }
  }
  reverse(all(P)), reverse(all(Q));
  int b = SUM<int>(P), c = SUM<int>(Q);
  return C<mint>(b + c, b) * hook_length_formula<mint>(P)
         * hook_length_formula<mint>(Q);
}

Back to top page