51Nod 1129. 机器人方阵(杨式矩阵与钩子公式)

日付: 10月 16, 2018

[机器人方阵问题 - 51Nod](https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1129)
## Problem
N个不同的数要排成杨式矩阵(Young tableaus，同行向右与同列向下递增)。问有多少种排法，对10007取模。

数据范围：$1 \le N \le 10^9$

## Solution
本题是个公式题，利用杨式矩阵的钩子公式(Hook Formula)可以直接解决。

记$F(n)$为含有$n$个元素的杨式矩阵的种数。钩子公式为：定义钩子长度$H(i,j)$为格点$(i,j)$下方、右方以及自身的格点总数。在给定了形状的情况下
$$F(n) = \frac{n!}{\prod H(i,j)}$$

P.S. 对于无形状限制的情况下
$$
F(n) = 
\begin{cases}
n & \quad n \le 2 \\
F(n-1) + (n-1)F(n-2) & \quad n \ge 3
\end{cases}
$$

此外还需注意，因为模数很小，在计算阶乘时很容易超过模数导致结果为0，因此算阶乘时应计算除去10007因子，剩下的乘积对10007的模以及模数项的指数。求阶乘时因为$n$很大，可以用周期和快速幂加速计算。

因为$N \le 10^9$，对于所有形状只需要$O(\sqrt{N})$枚举宽度，只有宽度为约数时才需要进一步计算，而约数个数大约是$O(log N)$，固定形状后计算的复杂度也是$O(\sqrt{N})$，因此总复杂度大约是$O(\sqrt{N}log N)$。

计算$F$时，分子和分母都需要先去除模数因子，然后比较一下看是否能够相互抵消，如果不能的话答案就是0，否则分子乘上分母逆元就可以了。

```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long ;
LL mpow(LL a, LL k, LL m) { LL r(1); for (a %= m; k; k >>= 1, a = a * a % m) if (k & 1)r = r * a % m; return r; }

// 51Nod. 1129
vector<int> inv_n(int n, int m = int(1e9 + 7)) {
    vector<int> Inv(n);
    Inv[1] = 1;
    for (int x = 2; x < n; x++) Inv[x] = Inv[m % x] * 1LL * (m - m / x) % m;
    return Inv;
}
const int Mod = 10007;
const auto Inv = inv_n(Mod, Mod);
pair<int, int> factorial(int n) {
    static vector<int> Cycle;
    if (Cycle.empty()) {
        Cycle.resize(Mod);
        Cycle[0] = 1;
        for (int i = 1; i < Mod; i++) Cycle[i] = Cycle[i - 1] * i % Mod;
    }
    int q = n / Mod;
    int x = mpow(Cycle.back(), q, Mod) * Cycle[n % Mod] % Mod, y = q;
    if (q) {
        auto p = factorial(q);
        x = x * p.first % Mod;
        y += p.second;
    }
    return {x, y};
}

int calc(int n, int m) {
    assert(n <= m);
    auto num = factorial(n * m);
    auto den = 1LL, mod0 = 0LL;
    mod0 += num.second;
    for (int i = 1; i < n; i++) {
        if (i % Mod == 0) {
            mod0 -= i;
            den = den * mpow(i / Mod, i, Mod) % Mod;
        } else den = den * mpow(i, i, Mod) % Mod;
        int j = n + m - i;
        if (j % Mod == 0) {
            mod0 -= i;
            den = den * mpow(j / Mod, i, Mod) % Mod;
        } else den = den * mpow(j, i, Mod) % Mod;
    }
    auto p1 = factorial(m), p2 = factorial(n - 1);
    int x = p1.first * Inv[p2.first] % Mod, y = p1.second - p2.second;
    den = den * mpow(x, n, Mod) % Mod;
    mod0 -= y * n;
    if (mod0 != 0) return 0;
    return num.first * Inv[den] % Mod;
}

int main() {
    int N;
    scanf("%d", &N);
    int ans = 0;
    for (int n = 1; n * n <= N; n++) {
        if (N % n) continue;
        int m = N / n, tmp = calc(n, m);
        ans += tmp;
        if (m != n) ans += tmp;
        ans %= Mod;
    }
    printf("%d\n", ans);
    return 0;
}
```
</details>

KONGROOの基地

このブログを検索

51Nod 1129. 机器人方阵(杨式矩阵与钩子公式)

コメント

コメントを投稿