G103469J Joke 题解

非常好题目啊。

APIO 之前有人给我推了这个题目，APIO 之后有人和我说这个题目和 T1 很像。

不过我没去 APIO 不知道啊。

题目可以转化为下面这个问题：有两条相互平行的链，每条从 指向 。同时两条链之间也有若干条无向边，保证每个点只和一条连接两条链的边连边。你需要给无向边定向使得图没有环。

对于 的情况，只需要在上链的 和下链的 之间连边即可。

对于没有环的情况，我们总是可以进行一次拓扑排序求出一组合法的方案。

不妨先考虑没有 的时候怎么做。考虑什么时候会成环。如果上面有一条指向下面的边，那么种点后面的节点就不能往前指。

如果有往上指向的边，那么终点后面的节点就不能往前指向。

简单来说，以下两种情况是不允许的。

有了图中这种边，就不能出现深蓝指向浅蓝色的边。

考虑钦定一条链，从左往右为每条边分配方向。

我们注意到，只有对未来的影响是重要的，因为之前的位置已经分配完毕。因此只有从下指向上的边是重要的。

具体的，我们需要知道从下指向上面的边下面的端点最远到哪里，这样如果有指向更前面的边，那么就必须也是从下指向上。

我们令 表示当前决定了前 个点对应边的方向，从下面指向上面的最远的点是 的方案数，例如，下面这张图对应 （没决定方向的边没有画）。

转移考虑枚举边的方向，判断合法不合法，如果是朝着上面指需要把 取 一下。这就是没有 的做法。

接下来考虑有 的时候怎么做。不妨先对着 做，因为 里面是没有 的。

首先如果已经有连边了就直接做即可。否则，我们需要选择一个点进行匹配。

我们注意到选择一个点匹配的时候需要知道哪些点选择过哪些点没选过，这个并不是很好维护。

我们发现我们有一个天然的界限可以用来维护哪些点没有选择。也就是 这个维度。这就是说，在 之后的点没有朝上指向的边。

我们继续观察，发现只有在 之后并且指向上面的边会影响状态。其余的边都不会影响。那么，我们不妨延迟这部分决策，对于不影响状态的情况，我们推迟到最后。

令 表示在之前 状态的基础上加一个 表示前面有几个 影响了状态（匹配了几个 ）。接下来考虑处理没有匹配的部分。我们发现，这些直接随便匹配就行，乘上一个阶乘就是答案。

这是因为不论你匹配到了哪一个点，因为对状态没有影响，因此边的朝向是唯一的。如果这个点在 之前，那么就只能朝上指，之后就只能朝下。

这样我们就做完了这个题目。

感觉很厉害。

参考代码：

#include <array>
#include <iostream>
#include <vector>

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

namespace maths {
template <ull mod, class int_type = ll, class uint_type = ull>
class modular {
  private:
    uint_type x;
    void norm() { x -= mod * (x >= mod); }

  public:
    modular() : x(0) {}
    modular(int_type _x) {
        if (_x < 0) {
            x = _x % (int_type)mod + (int_type)mod;
        }
        else {
            x = _x % mod;
        }
        norm();
        return;
    }
    friend modular operator+(const modular &lhs, const modular &rhs) {
        modular ret;
        ret.x = lhs.x + rhs.x;
        ret.norm();
        return ret;
    }
    friend modular operator-(const modular &lhs, const modular &rhs) {
        modular ret;
        ret.x = lhs.x + mod - rhs.x;
        ret.norm();
        return ret;
    }
    friend modular operator*(const modular &lhs, const modular &rhs) {
        return modular(lhs.x * rhs.x);
    }
    modular operator-() const {
        modular ret;
        ret.x = mod - x;
        return ret;
    }
    modular operator-=(const modular &b) { return *this = *this - b; }
    modular operator+=(const modular &b) { return *this = *this + b; }
    modular operator*=(const modular &b) { return *this = *this * b; }
    bool operator==(const modular &b) const { return x == b.x; }
    uint_type val() const { return x; }
    friend std::istream &operator>>(std::istream &is, modular &rhs) {
        is >> rhs.x;
        rhs.x %= mod;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const modular &rhs) {
        os << rhs.val();
        return os;
    }
};
} // namespace maths

namespace maths {
template <class T>
T quick_pow(T a, ull b, T id = T()) {
    T ret = id;
    for (; b; b >>= 1, a = a * a) {
        if (b & 1) {
            ret = a * ret;
        }
    }
    return ret;
}

template <class T>
T quick_pow(T a, const std::string &s, T id = T()) {
    T ret = id;
    for (size_t i = 0; i < s.size(); i++, a = a * a) {
        if (s[i] == '1') {
            ret = a * ret;
        }
    }
    return ret;
}

} // namespace maths

namespace maths {
const uint mod = 998244353;
using mll = maths::modular<mod>;
std::vector<mll> fact{1};
std::vector<mll> inv{1};

mll factorial(uint x) {
    for (size_t i = fact.size(); i <= x; i++) {
        fact.push_back(fact.back() * i);
    }

    return fact[x];
}

mll inv_frac(uint x) {
    for (size_t i = inv.size(); i <= x; i++) {
        inv.push_back(inv.back() * maths::quick_pow<mll>(i, mod - 2, 1));
    }

    return inv[x];
}

mll choose(int n, int m) {
    if (n < 0 || m > n) {
        return 0;
    }
    else {
        return factorial(n) * inv_frac(m) * inv_frac(n - m);
    }
}
} // namespace maths

namespace solve {
const uint MOD = 998244353;
using mll = maths::mll;
const uint N = 105;

const uint npos = -1;

void solve() {
    uint n;
    std::cin >> n;

    std::vector<uint> p(n), q(n);

    for (size_t i = 0; i < n; i++) {
        std::cin >> p[i];
        --p[i];
    }

    for (size_t i = 0; i < n; i++) {
        std::cin >> q[i];
        --q[i];
    }

    std::vector<uint> to(n);

    for (size_t i = 0; i < n; i++) {
        to[p[i]] = q[i];
    }

    std::vector<uint> missing_number;

    {
        std::vector<bool> vis(n);
        for (size_t i = 0; i < n; i++) {
            if (q[i] == npos) {
                continue;
            }

            vis[q[i]] = true;
        }

        for (size_t i = 0; i < n; i++) {
            if (!vis[i]) {
                missing_number.push_back(i);
            }
        }
    }

    std::array<std::array<std::array<mll, N>, N>, N> dp;

    for (auto &&i : dp) {
        for (auto &&j : i) {
            j.fill(0);
        }
    }

    dp[0][0][0] = 1;

    for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j <= n; j++) {
            for (size_t k = 0; k <= n; k++) {
                if (dp[i][j][k] == 0) {
                    continue;
                }
                /**
                 * 当前状态。
                 *
                 * 前 i 个。最远指向前面的是 j。
                 *
                 * 匹配了 k 对。
                 */

                if (to[i] == npos) {
                    /**
                     * 轮空。选择默认的。
                     */
                    dp[i + 1][j][k] += dp[i][j][k];

                    /**
                     * 扩展，不选择默认情况。
                     */

                    for (auto &&nxt : missing_number) {
                        if (nxt + 1 <= j) {
                            continue;
                        }
                        dp[i + 1][nxt + 1][k + 1] += dp[i][j][k];
                    }
                }
                else {
                    if (to[i] + 1 > j) {
                        /**
                         * 可以指向下面。
                         */
                        dp[i + 1][j][k] += dp[i][j][k];
                    }

                    dp[i + 1][std::max<uint>(j, to[i] + 1)][k] += dp[i][j][k];
                }
            }
        }
    }

    mll ans = 0;
    for (size_t j = 0; j <= n; j++) {
        for (size_t k = 0; k <= missing_number.size(); k++) {
            ans += dp[n][j][k] * maths::factorial(missing_number.size() - k);
        }
    }

    std::cout << ans << std::endl;
}
} // namespace solve

int main() {
    solve::solve();
    return 0;
}