UNR#3 Day2

A. 白鸽

是否有解即判欧拉回路，判每个结点的度数是否都是偶数和有边的的结点是否与 \(1\) 号结点连通即可。

因为最后形成的是一个封闭图形，大可把 \(x\) 轴正方向看做一条射线，我们每由上至下穿过这条射线会对答案产生 \(1\) 的贡献，反之，从下至上穿过这条射线就会对答案产生 \(-1\) 的贡献。

问题转化为给欧拉回路上的无向边定向，使其在仍是一个欧拉回路的使答案最大。

先钦定所有 \(y\) 轴右侧穿过 \(x\) 轴的的边的方向都是由上至下，即所有边的方向是顺时针，然后初步统计一个圈数出来，这个圈数不小于答案。

然后考虑给边重定向，即有些边需要反向，也即把边分成两部分，一部分维持原样，一部分反向，且仍满足欧拉回路的要求，其中 \(y\) 轴右侧的边反向后需付出 \(2\) 的代价（原来 \(+1\)，现在 \(-1\)），使付出的代价最小。

这么说其实做法就显然了，就是在求一个最小费用最小割，费用流即可。

具体地，对 \(y\) 轴右侧穿过 \(x\) 轴的边，建流量为 \(1\)，费用为 \(2\) 的 反边，其余的边建流量为 \(1\)，费用为 \(0\) 的边。统计每个网络中结点的度数（入度为 \(ind_i\)，出度为 \(oud_i\)）。

建超级源、汇点 \(S, T\)，枚举每个结点，若当前结点 \(i\) 满足：

• \(ind_i < oud_i\)，连边 \(S \to i\)，流量为 \(\dfrac{oud_i - ind_i}2\)，费用为 \(0\)。
• \(oud_i > ind_i\)，连边 \(i \to T\)，流量为 \(\dfrac{ind_i - oud_i}2\)，费用为 \(0\)。

类似地，因为边反向后会使点的入度和出度同时发生变化，所以流量带了一个 \(\dfrac12\) 的系数。

建出图跑 Dinic 即可，因为是单位容量网络，Dinic 的时间复杂度是 \(\mathcal O(m^\frac34)\)。

又因为费用只有 \(-2, 0, 2\) 两种，很容易维护 SPFA 队列的有序，此时的 SPFA 的时间复杂度近似于线性，即 \(\mathcal O(m)\)。

所以总的时间复杂度就是 \(\mathcal O(m^\frac74)\)。

代码 ：

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 2e4 + 10, S = N - 1, T = N - 2, INF = 0x3f3f3f3f;

int n, m, x[N], y[N], c[N], d[N];
bool vis[N];

namespace DSU {
    int fa[N];
    inline void init(int n) {iota(fa + 1, fa + n + 1, 1);}
    inline int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
    inline void merge(int x, int y) {fa[find(y)] = find(x);}
}

int tot = 1, head[N];
struct Edge {int to, nxt, w, c;} e[N << 2];
inline void add(int u, int v, int w, int c) {
    e[++tot] = Edge{v, head[u], w, c}, head[u] = tot;
    e[++tot] = Edge{u, head[v], 0, -c}, head[v] = tot;
}

int dinic() {
    int totfl = 0, totc = 0;

    deque<int> q;

    auto spfa = [&]() -> bool {
        memset(c, 0x3f, sizeof(c)), c[S] = 0, q.emplace_back(S);
        while (!q.empty()) {
            int u = q.front(); q.pop_front();
            vis[u] = 0;
            for (int i = head[u], v; v = e[i].to, i; i = e[i].nxt) if (e[i].w && c[u] + e[i].c < c[v]) {
                c[v] = c[u] + e[i].c;
                if (!vis[v]) vis[v] = 1, (e[i].c > 0 ? q.emplace_back(v) : q.emplace_front(v));
            }
        }
        return c[T] < INF;
    };

    auto dfs = [&](auto &&self, int u, int cf) -> int {
        if (u == T) return cf;
        vis[u] = 1; int rf = 0;
        for (int i = head[u], v; v = e[i].to, i; i = e[i].nxt) if (!vis[v] && e[i].w && c[v] == c[u] + e[i].c) {
            int tf = self(self, v, min(cf, e[i].w));
            if (tf) {
                cf -= tf, rf += tf;
                e[i].w -= tf, e[i ^ 1].w += tf;
                if (!cf) break;
            }
        }
        vis[u] = 0; if (!rf) c[u] = INF;
        return rf;
    };

    memset(vis, 0, sizeof(vis));
    while (spfa()) totc += dfs(dfs, S, INF) * c[T];
    return totc;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
    DSU::init(n);
    int ans = 0;
    while (m--) {
        int i, j; cin >> i >> j;
        vis[i] = vis[j] = 1; DSU::merge(i, j);
        if (1ll * x[i] * y[j] > 1ll * x[j] * y[i]) swap(i, j);
        if (y[i] >= 0 && y[j] < 0) add(i, j, 1, 2), ans++;
        else add(i, j, 1, 0);
        d[i]--, d[j]++;
    }
    for (int i = 1; i <= n; i++) if (vis[i] && (DSU::find(i) != DSU::find(1) || d[i] & 1)) {cout << "-1"; return 0;}
    for (int i = 1; i <= n; i++) d[i] < 0 ? add(S, i, -d[i] >> 1, 0) : add(i, T, d[i] >> 1, 0);
    cout << ans - dinic() << '\n';
    return 0;
}

B. 百鸽笼

记 \(m = \max a_i\)。

留一个不住总感觉怪怪的，干脆把题意转化为 \(\sum a_i\) 个人住，求每列最后一个住满的概率。

容斥，需要求每列在某些列前住满的概率。

设当前列要在某 \(k\) 列住满前住满，那么其余列如何我们都不关心，可以直接忽略。

问题来到对于一个序列，其中 \(i\) 出现次数为 \(a_i\)，\(j\)（代表“某些列”）出现次数 \(< a_j\)，且 \(i\) 最后出现，设其长度为 \(l\)，求其对答案的贡献。

由条件，该序列上每一个点都有 \(m + 1\) 种选择（因为第 \(i\) 列是第一个填满的，填的过程中每一列都不满，都能填），所以它对答案的贡献就是 \(\left(\dfrac1{k + 1}\right)^l\)。

DP。

设 \(f_i\) 表示序列长度为 \(i\) 时对答案的贡献，枚举每一列上住了多少人来转移。

因为同一列的选择间是等价的，所以若当前列选了 \(t\) 个人，则对 \(f_i\) 的贡献要乘上 \(\dfrac1{t!}\)，最后每个 \(f_i\) 再乘上 \(i!\)。

DP 的时间复杂度是 \(\mathcal O(nm^2)\)。

需要枚举的是“某 \(k\) 列”和最后填满的列，所以总时间复杂度是 \(\mathcal O(2^nn^2m^2)\)。

枚举“某 \(k\) 列”的 \(\mathcal O(2^n)\) 过于朴素，实际上我们并不关心究竟选出来了哪些列，所以可以把选中的列数写进状态里，每一列根据选或不选来转移即可，DP 的时间复杂度是 \(\mathcal O(n^3m^2)\)。

我们同样需要枚举最后填满的列，所以总时间复杂度是 \(\mathcal O(n^4m^2)\)。

非常跑不满，所以实现好的话是可过的，但是离稳过还差点。

枚举最后填满的列也是多余的，把填满的列也归到“某 \(k\) 列”中，最后对 \(\mathcal O(n^2m)\) 个状态 \(\mathcal O(nm)\) 枚举每一列的状态算答案即可，时间复杂度 \(\mathcal O(n^3m^2)\)。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr int N = 40, M = 910, MOD = 998244353;

int n, m, nm, a[N];
ll fct[M], inv[M], ifct[M], f[N][M], g[N][M];

ll qp(ll base, int e) {
    ll res = 1;
    while (e) {
        if (e & 1) res = res * base % MOD;
        base = base * base % MOD;
        e >>= 1;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], m += a[i];

    fct[0] = fct[1] = ifct[0] = ifct[1] = inv[1] = 1;
    for (int i = 2; i <= m; i++) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
    for (int i = 2; i <= m; i++) fct[i] = fct[i - 1] * i % MOD, ifct[i] = ifct[i - 1] * inv[i] % MOD;

    m = 0, f[0][0] = 1;
    for (int i = 1; i <= n; m += a[i++]) {
        for (int j = i - 1; j >= 0; j--) {
            for (int k = m; k >= 0; k--) if (f[j][k]) {
                for (int l = 0; l < a[i]; l++) {
                    f[j + 1][k + l] = (f[j + 1][k + l] + f[j][k] * ifct[l]) % MOD;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        ll ans = 0;
        for (int j = 0; j < n; j++) {
            for (int k = 0; k <= m; k++) if (g[j][k] = f[j][k]) {
                if (j) for (int l = max(0, k - a[i] + 1); l <= k; l++) g[j][k] = (g[j][k] - g[j - 1][l] * ifct[k - l]) % MOD;
                if (g[j][k]) ans = (ans + g[j][k] * ((j & 1) ? -1 : 1) * fct[k + a[i] - 1] % MOD * qp(inv[j + 1], k + a[i])) % MOD;
            }
        }
        cout << (ans * ifct[a[i] - 1] % MOD + MOD) % MOD << ' ';
    }
    return 0;
}

C. 鸽举选仕