Hook length formula (フック長公式)
(combinatorics/hook_length_formula.hpp)

• View this file on GitHub
• Last update: 2022-12-07 22:57:01+09:00
• Include: #include "combinatorics/hook_length_formula.hpp"
• Link: https://yukicoder.me/problems/no/2149

ヤング盤に対するフック長公式．

使用方法

vector<int> a;

mint ret = hook_length_formula<mint>(a);

計算量は $n = \mathrm{len}(a)$ として $O(n \log n + \mathrm{sum}(a))$．

問題例

• C - Numbering Blocks
• No.2149 Vanitas Vanitatum - yukicoder

Links

• フック長の公式 - Wikipedia

Verified with

• combinatorics/test/hook_length_formulat.yuki2149.test.cpp

Code

#include <algorithm>
#include <vector>

// Hook length formula
// Complexity: O(sum(hook))
// Verify: https://yukicoder.me/problems/no/2149
template <class T> T hook_length_formula(std::vector<int> hook) {
    if (hook.empty()) return T(1);
    std::sort(hook.begin(), hook.end());
    std::vector<int> len(hook.back());
    T num(1), den(1);
    int sum = 0;
    for (int l : hook) {
        for (int j = 0; j < l; ++j) num *= ++sum, den *= (++len.at(j)) + l - 1 - j;
    }
    return num / den;
}

#line 1 "combinatorics/hook_length_formula.hpp"
#include <algorithm>
#include <vector>

// Hook length formula
// Complexity: O(sum(hook))
// Verify: https://yukicoder.me/problems/no/2149
template <class T> T hook_length_formula(std::vector<int> hook) {
    if (hook.empty()) return T(1);
    std::sort(hook.begin(), hook.end());
    std::vector<int> len(hook.back());
    T num(1), den(1);
    int sum = 0;
    for (int l : hook) {
        for (int j = 0; j < l; ++j) num *= ++sum, den *= (++len.at(j)) + l - 1 - j;
    }
    return num / den;
}

Back to top page