ABC378 每日一寄1st

ABC378 G - Everlasting LIDS (1st)

(是每日一寄的开始，虽然好像做不到每日一寄啦)

相关算法：序理论，杨表，钩长公式，dp

Part 1.题目概述

题意很简单，给定限定\(A,B\)，要求构造出长为\(A\cdot B-1\)的且具有以下性质的排列\(P\)：
1. 最长上升子序列(LIS)为\(A\).
2. 最长下降子序列(LDS)为\(B\).
3. 存在一个整数\(n\)使得在\(P\)的末尾添加\(n+0.5\)不会改变最长递增子序列和最长递减子序列的长度

求可行的构造方案数，结果输出方案数模素数\(M\)。

Part 2.杨表

解决这题需要一些前置知识：杨表
英式画法的杨表由有限个相邻的方格排列而成，其中，各横行的左边对齐，长度从上到下递增。
标准杨表：在杨表的 n个方格中任意填入1到n中的相异正整数，各行和各列中的数字皆严格递增。
显然，杨表代表着一种二维表示的偏序。而这种拓扑序可以与一个排列的LIS和LDS相关联。
引入RSK算法(杨表的插入算法)：
令 \(S\) 是一个杨表，定义 \(S \leftarrow x\) 表示将 \(x\) 从第一行插入杨表中，具体如下：(引自oiwiki)
1. 在当前行中找到最小的比 \(x\) 大的数 \(y\) 。
2. 如果找到了，用 \(x\) 去替换 \(y\)，移到下一行，令 \(x \leftarrow y\) 重复操作1。
3. 如果找不到，就把 \(x\) 放在该行末尾并退出。记 \(x\) 在第 \(s\) 行第 \(t\) 列，\((s, t)\) 必定是一个边角。一个格子 \((s, t)\) 是边角当且仅当 \((s + 1, t)\) 和 \((s, t + 1)\) 都不存在格子。

对于一个排列 \(P = \{p_1,p_2,...p_n\}\),我们构造一个杨表
\[S = \emptyset \leftarrow p_1 \leftarrow p_2 \leftarrow ... \leftarrow p_n\] 此外，我们定义一个记录表 \(Q\)，\(Q_{s,t}\) 为插入 \(S\) 位置 \((s,t)\) 时元素 \(p_i\) 的下标 \(i\)。
可以预见:
1. \(Q\) 中元素也满足杨表的偏序关系(构造时是在已有格子的下方或右方插入更大的元素),故 \(Q\) 也是一个杨表。
2. 且 \(S\) 和 \(Q\) 具有相同的形状(这是易从定义推出的)。

于是，通过一个排列 \(P\)，我们生成了一对杨表 \(\{S,Q\}\)。 将 \(n\) 元排列的集合记作 \(\mathbb{P}\),\(n\) 元杨表的集合记作 \(\mathbb{S}\),具有相同形状的杨表集合记作 \(\mathbb{S_{\lambda_i}}\),其中 \(\lambda\) 是整数 \(n\) 的一个分拆，这唯一对应了杨图的一个形状。 用 \(\pi_\lambda\) 表示这样形状的一个杨表。

以下不加证明给出一些结论,符号与上文意义保持一致:
1. \(P\) 的LIS等于 \(S\) 的第一行元素个数，LDS等于 \(S\) 的第一列元素个数。
2. \(f : \mathbb{P} \rightarrow \sum_{\lambda \vdash n} \mathbb{S_{\lambda}} \times \mathbb{S_{\lambda}}\)是双射。即从使用上文所属的RSK插入算法，不同排列得到的杨表对是不同的(单射)。更为重要的是这还是一个满射，也就是说可以得到所有的杨表对。因此也有：\[n! = A^n_n = \sum_{\lambda \vdash n}{(\dim \pi_{\lambda})}^2\]
3. 对于对于杨表中的一个方格 \(v\)，定义其勾长 \(\mathrm{hook}(v)\) 等于同行右边的方格数加上同列上面的方格数，再加 \(1\) （即方格本身）。如果用 \(\dim \pi_{\lambda}\) 表示这样的方法个数，方法个数就等于 \(n!\) 除以所有方格的勾长的乘积。
有钩长公式:\[\dim \pi _{\lambda} = \frac{n!}{\prod_{x \in Y(\lambda)} \mathrm{hook}(x)}\]

现在，我们有了足够的理论基础来解决本题。

Part 3.分析

由Part 2中的理论，长为 \(A\cdot B - 1\) 的排列对应的杨表形状是唯一的，即一个 \(A \times B\) 的矩形去掉右下角一块。而条件3要求我们在 \(P\) 的末尾插入元素 \(n + 0.5\) 后LIS和LDS不变，那么对应的杨图应为 \(A \times B\) 的矩形了。
考虑前面所述的RSK插入算法，对原杨表 \(\pi\) 插入一个元素后刚好到达右下角，那么只能是每次替换掉该行最后一个元素，然后向下传递。我们选取的元素应该为介于 \(\pi_{1,b-1}\) 和 \(\pi_{1,b}\)，即\(\pi_{1,b-1} < n+0.5<\pi_{1,b}\) 。然后，这个数替换掉 \(\pi_{1,b}\) , \(\pi_{1,b}\) 接着向下传递，仍然重复这样的替换，那么条件是相似的。由于杨表的性质，已经有了 \(\pi_{i,b}<\pi_{i+1,b}\) ,故我们只需要求 \(\pi_{i+1,b-1}<\pi_{i,b}\) ,便可以保持这种传递一直进行到最后一行。
而构造出这样特定的杨表后，我们有 \(\dim \pi _{\lambda}\) 种记录表将其映射成一个合法的排列 \(P\) (考虑我们前面所述的双射和映上性)。所以我们求解这道题，只需得到满足条件杨表的数量和 \(\dim \pi _{\lambda}\) ，而后者只需要使用钩长公式即可。

Part 4.实现(DP)

我们考虑使用dp来求解合法的杨表数量。
模拟杨表的填入，我们顺序选取元素 \(1 \sim A\cdot B-1\) 填入，以减少不必要的check。
考虑杨表的二维偏序性，我们不是在二维的矩阵上去枚举填入数字的位置，而是选择一维顺序填入，另一维枚举填入位置。(毕竟顺序选取元素时跨越式的填入是一定不符合杨表的限制的)
为了方便检查分析的来的条件，我们顺序填入行，并枚举填入的列号。用一个vector \(v\) 来表示每列填入了多少行，设计状态\(dp[v]\)表示填入状态为\(v\)的方案数。我们顺序选取元素 \(1 \sim A\cdot B-1\) 填入，对于每个元素，我们枚举前一个元素填入后的所有状态，对每个状态枚举填入某列是否合法，若合法则从 \(v\) 转移到合法状态 \(u\) 。状态转移方程：
\[dp[u] += dp[v]\] 对 \(v\) 填入第 \(i\) 列合法所需的条件:
1. \(v[i] \neq a \bigwedge (i = 0 \bigvee v[i] < v[i - 1])\)
2. \(i \neq b - 1 \bigvee v[i] < v[i - 1] - 1\)

我们用一个map来滚动记录状态并且dp。

code:(用了jls的模数板子，并且借鉴了一下别的大佬的思路)

void solve()
{
    int a, b, m;
    cin >> a >> b >> m;
    MInt<0>::Mod = m;
    using Z = MInt<0>;

    Z ans = 1;
    for (int x = 0; x < a * b - 1; x++) {
        int i = x / b, j = x % b;
        ans *= (x+1);
        int q = (a + b - i - j - 1 - (i == a - 1) - (j == b - 1));
        ans /= q;
    }
    
    map<vector<int>, Z>dp;
    dp[vector<int>(b,0)] = 1;
    for (int i = 0; i < a * b - 1; i++) {
        map<vector<int>, Z>ndp;
        for (auto &[v, c] : dp) {
            for (int i = 0; i < b; i++) {
                if (v[i] != a && (i == 0 || v[i] < v[i - 1])) {
                    if (i != b - 1 || v[i] < v[i - 1] - 1) {
                        auto u = v;
                        u[i]++;
                        ndp[u] += c;
                    }
                }
            }
        }
        dp = move(ndp);
    }
    vector<int>getans(b, a);
    getans[b - 1]--;
    ans *= dp[getans];
    cout << ans << endl;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
        solve();
    return 0;
}

模数板子：

template<class T>
constexpr T power(T a, i64 b) {
    T res{ 1 };
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}

template<i64 P>
struct MInt {
    i64 x;
    constexpr MInt() : x{ 0 } {}
    constexpr MInt(i64 x) : x{ norm(x % getMod()) } {}

    static i64 Mod;
    constexpr static i64 getMod() {
        if (P > 0) {
            return P;
        }
        else {
            return Mod;
        }
    }
    constexpr static void setMod(i64 Mod_) {
        Mod = Mod_;
    }
    constexpr i64 norm(i64 x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr i64 val() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        return power(*this, getMod() - 2);
    }
    constexpr MInt& operator*=(MInt rhs)& {
        if (getMod() < (1ULL << 31)) {
            x = x * rhs.x % int(getMod());
        }
        else {
            x = mul(x, rhs.x, getMod());
        }
        return *this;
    }
    constexpr MInt& operator+=(MInt rhs)& {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt& operator-=(MInt rhs)& {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt& operator/=(MInt rhs)& {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream& operator>>(std::istream& is, MInt& a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream& operator<<(std::ostream& os, const MInt& a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
    friend constexpr bool operator<(MInt lhs, MInt rhs) {
        return lhs.val() < rhs.val();
    }
};

template<>
i64 MInt<0>::Mod = 998244353;

//constexpr int P = 1000000007;
//using Z = MInt<P>;