F. Dora 的颜料 详细题解

问题重述

给定一个 $n \times n$ 的矩阵 $a$，其中 $m$ 个位置为 $1$，其余为 $2$。真实矩阵 $b$ 与 $a$ 恰好有一个位置不同（$1$ 变 $2$ 或 $2$ 变 $1$）。定义矩阵的美丽值为用最少操作（整行涂 $2$ 或整列涂 $1$）将全 $0$ 矩阵变成该矩阵的方案数。求 $b$ 的期望美丽值，所有 $n^2$ 种可能错误等概率。

关键观察

观察 1：转化为图论问题

将每行视为一个节点（行节点），每列视为一个节点（列节点），共 $2n$ 个节点。对于矩阵中的每个 $1$，在对应的行节点和列节点之间连一条有向边（方向？）。

实际上，涂色过程可以理解为：

• 涂一列 $j$ 为 $1$ 相当于给所有行节点到列节点 $j$ 的边？
• 需要更精确的建模

标准模型：将矩阵 $b$ 的构造看作一个二分图：

• 左部：$n$ 个行节点
• 右部：$n$ 个列节点
• 若 $b_{i,j} = 1$，则存在有向边 $i \to j$
• 若 $b_{i,j} = 2$，则存在有向边 $j \to i$（或理解为反向）

观察 2：最小操作数 $f(b)$ 与拓扑排序

构造一个有向图 $G$，节点为 $2n$ 个（$n$ 行 $+$ $n$ 列）。对于矩阵中的每个 $1$，添加一条从行节点到列节点的边；对于每个 $2$，添加一条从列节点到行节点的边。

重要结论：$f(b)$ 等于该有向图的最长路径长度（或拓扑排序的层数）。实际上，$f(b) =$ 拓扑排序的层数 $-$ 1。

观察 3：美丽值的计算公式

设拓扑排序后，第 $k$ 层有 $r_k$ 个行节点和 $c_k$ 个列节点。则美丽值为：

因为每一层内的节点可以任意排列顺序（它们之间没有边约束）。

观察 4：初始矩阵的美丽值计算

给定 $a$（$m$ 个 $1$，其余 $2$），可以计算其有向图的拓扑排序，得到每层的行/列计数，进而计算美丽值。

若图中存在环，则无法拓扑排序，美丽值为 $0$。

观察 5：修改一个元素的影响

修改一个元素（翻转 $1$ 和 $2$）相当于：

• 删除一条原有向边
• 添加一条反向有向边

这只会影响拓扑排序中相邻两层的节点计数，因此可以 $O(1)$ 更新美丽值。

观察 6：环的处理

当初始图有环时（美丽值 $= 0$），需要找到包含修改位置的最小环（通常是 $4$ 元环），然后计算翻转后是否消除环。

算法步骤

1. 建图：根据给定的 $m$ 个 $1$ 的位置，建立有向图

   • 对于每个 $1$ 在 $(x,y)$：添加边 $x \to y$（行 $\to$ 列）
   • 对于每个 $2$ 的位置（其余 $n^2-m$ 个）：添加边 $y \to x$（列 $\to$ 行）

2. 计算初始美丽值：

   • 进行拓扑排序，记录每层的行/列数量
   • 若存在环，美丽值为 $0$，记录环信息

3. 若初始美丽值 $\ne 0$：

   • 对于每个可能修改的位置，计算翻转后美丽值的变化
   • 由于翻转只影响 $O(1)$ 个层，可以快速计算
   • 求和后除以 $n^2$ 得到期望

4. 若初始美丽值 $= 0$：

   • 找到导致环的关键边
   • 只有翻转某些边才能消除环
   • 枚举这些边，计算翻转后的美丽值

时间复杂度

• 建图：$O(n + m)$
• 拓扑排序：$O(n + m)$
• 计算期望：$O(n + m)$
• 总复杂度：$O(n + m)$

完整代码

#include<bits/stdc++.h>
using namespace std;

#define MOD         998244353
#define int         long long
#define pii         pair<int,int>
#define REP(i,b,e)  for(int i=(b);i<(e);++i)

int qpow(int a, int b, int m = MOD, int res = 1) {
    a %= m;
    while (b > 0) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

int fac[2000005], inv[2000005], si[2000005];

void init(int n) {
    fac[0] = inv[0] = si[0] = 1;
    REP(i, 1, n + 1) fac[i] = fac[i - 1] * i % MOD;
    inv[n] = qpow(fac[n], MOD - 2);
    for (int i = n - 1; i >= 1; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;
    REP(i, 1, n + 1) si[i] = inv[i] * fac[i - 1] % MOD;
}

int binom(int x, int y) {
    return (x < y || y < 0) ? 0 : fac[x] * inv[y] % MOD * inv[x - y] % MOD;
}

// 快速 IO
namespace fastIO {
    const int BUF_SIZE = 6000010;
    char buf[BUF_SIZE];
    int p = BUF_SIZE, pend = BUF_SIZE;
    
    inline char nc() {
        if (p == pend) {
            p = 0;
            pend = fread(buf, 1, BUF_SIZE, stdin);
            if (pend == 0) return -1;
        }
        return buf[p++];
    }
    
    inline bool blank(char ch) {
        return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
    }
    
    inline void read(int &x) {
        char ch;
        while (blank(ch = nc()));
        if (ch == -1) return;
        for (x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
    }
}

using namespace fastIO;

int n, m;
int a[200005], b[200005];      // a: 行出度, b: 列出度
vector<pii> edges;              // 所有 1 的位置
int d1[200005], d2[200005];     // 拓扑排序层数
int visa[200005], visb[200005];
vector<int> h[200005];          // 邻接表（用于环检测）
vector<int> nodes[200005], buc[200005];
int X, Y;                       // 环中关键点的位置
int id1[200005], id2[200005];
int cnt[400005];                // 每层计数

// 拓扑排序，计算美丽值
int solve() {
    // 清空桶
    for (int i = 0; i <= n; i++) buc[i].clear();
    for (int i = 0; i < n; i++) buc[a[i]].push_back(i);
    
    int num = 0;
    for (int i = 0; i <= n; i++) {
        for (auto j : buc[i]) id1[num++] = j;
    }
    
    for (int i = 0; i <= n; i++) buc[i].clear();
    for (int i = 0; i < n; i++) buc[b[i]].push_back(i);
    
    num = 0;
    for (int i = 0; i <= n; i++) {
        for (auto j : buc[i]) id2[num++] = j;
    }
    
    for (int i = 0; i < n; i++) d1[i] = d2[i] = -1;
    
    int ans = 1, x = 0, y = 0, cur = 0;
    
    while (x < n || y < n) {
        if (x < n && a[id1[x]] <= y) {
            int sum = 0;
            while (x < n && a[id1[x]] <= y) {
                ++sum;
                d1[id1[x++]] = cur;
            }
            if (cur) ans = ans * fac[sum] % MOD;
        } else if (y < n && b[id2[y]] <= x) {
            int sum = 0;
            while (y < n && b[id2[y]] <= x) {
                ++sum;
                d2[id2[y++]] = cur;
            }
            if (cur) ans = ans * fac[sum] % MOD;
        } else {
            X = x; Y = y;
            return 0;   // 存在环
        }
        ++cur;
    }
    return ans;
}

// 翻转边 (x, y) 后重新计算美丽值
int update_edge(int x, int y) {
    bool found = false;
    for (auto e : edges) {
        if (e.first == x && e.second == y) {
            found = true;
            break;
        }
    }
    
    int ret;
    if (found) {
        // 删除边 (x, y)
        --b[y];
        ++a[x];
        ret = solve();
        ++b[y];
        --a[x];
    } else {
        // 添加边 (x, y)
        ++b[y];
        --a[x];
        ret = solve();
        --b[y];
        ++a[x];
    }
    return ret;
}

void Main() {
    read(n); read(m);
    edges.clear();
    
    for (int i = 0; i < n; i++) a[i] = b[i] = 0;
    for (int i = 0; i < n * 2 + 2; i++) cnt[i] = 0;
    for (int i = 0; i < n; i++) visa[i] = visb[i] = 0;
    for (int i = 0; i < n; i++) h[i].clear();
    for (int i = 0; i < n; i++) nodes[i].clear();
    
    // 初始：所有位置默认为 2（列 -> 行）
    for (int i = 0; i < n; i++) {
        a[i] = n;      // 每行有 n 条出边（到所有列）
        b[i] = 0;      // 每列初始出度为 0
    }
    
    for (int i = 0; i < m; i++) {
        int x, y;
        read(x); read(y);
        --x; --y;
        edges.push_back({x, y});
        // 将 (x, y) 从 2 改为 1：删除边 y->x，添加边 x->y
        ++b[y];        // 列 y 的出度 +1（因为有了 x->y）
        --a[x];        // 行 x 的出度 -1（因为删除了 y->x）
    }
    
    // 调整偏移（使 a[i] 非负）
    for (int i = 0; i < n; i++) a[i] += n;
    
    int ans = solve();
    
    if (!ans) {
        // 初始图有环，美丽值为 0
        if (X == n - 1 || Y == n - 1) {
            cout << 0 << "\n";
            return;
        }
        
        int x = id1[X], y = id2[Y];
        bool found = false;
        for (auto e : edges) {
            if (e.first == x && e.second == y) {
                found = true;
                break;
            }
        }
        
        if (found) {
            // 标记与 x 同列和与 y 同行的节点
            for (auto e : edges) {
                if (e.first == x) visb[e.second] = 1;
                if (e.second == y) visa[e.first] = 1;
            }
            X = Y = -1;
            for (auto e : edges) {
                if (e.first != x && e.second != y) {
                    if (!visa[e.first] && !visb[e.second]) {
                        X = e.first;
                        Y = e.second;
                        break;
                    }
                }
            }
            if (X == -1) {
                cout << 0 << "\n";
                return;
            }
        } else {
            X = Y = -1;
            // 构建邻接表
            for (auto e : edges) h[e.first].push_back(e.second);
            
            int sum = 0;
            for (auto j : h[x]) {
                visa[j] = 1;
                ++sum;
            }
            
            for (int i = 0; i < n; i++) {
                bool has_y = false;
                for (auto j : h[i]) {
                    if (j == y) {
                        has_y = true;
                        break;
                    }
                }
                if (!has_y) continue;
                
                vector<int> z;
                for (auto j : h[i]) {
                    if (visa[j]) {
                        visa[j] = 0;
                        --sum;
                        z.push_back(j);
                    }
                }
                if (sum) {
                    X = i;
                    for (int j = 0; j < n; j++) {
                        if (visa[j]) {
                            Y = j;
                            break;
                        }
                    }
                    break;
                }
                for (auto j : z) {
                    ++sum;
                    visa[j] = 1;
                }
            }
            if (X == -1) {
                cout << 0 << "\n";
                return;
            }
        }
        
        int x2 = X, y2 = Y;
        int sum_beauty = update_edge(x, y) + update_edge(x, y2) + 
                         update_edge(x2, y) + update_edge(x2, y2);
        cout << sum_beauty % MOD * qpow(n * n % MOD, MOD - 2) % MOD << "\n";
        return;
    }
    
    // 初始美丽值不为 0
    for (int i = 0; i < n; i++) {
        ++cnt[d1[i]];
        ++cnt[d2[i]];
    }
    
    int res = 0;
    // 层 0 的贡献
    res = (res + ans * cnt[0] % MOD * (cnt[1] == 1 ? cnt[2] + 1 : 1)) % MOD;
    // 层 1 和层 2 的贡献
    if (cnt[2] && cnt[1]) {
        res = (res + ans * (cnt[2] == 1 ? cnt[3] + 1 : 1)) % MOD;
    }
    // 相邻层的贡献
    for (int i = 2; i < 2 * n - 1; i++) {
        if (cnt[i] && cnt[i + 1]) {
            int term = (cnt[i + 1] == 1 ? cnt[i + 2] + 1 : 1) % MOD;
            term = term * (cnt[i] == 1 ? cnt[i - 1] + 1 : 1) % MOD;
            res = (res + ans * term) % MOD;
        }
    }
    
    cout << res * qpow(n * n % MOD, MOD - 2) % MOD << "\n";
}

void TC() {
    init(1000000);
    int tc = 1;
    read(tc);
    while (tc--) {
        Main();
        cout.flush();
    }
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    TC();
    return 0;
}

总结

本题的核心技巧：

1. 将矩阵涂色问题转化为二分图有向边问题
2. 最小操作数 = 拓扑排序层数
3. 美丽值 = 每层节点数的阶乘乘积
4. 翻转一条边只影响 $O(1)$ 个层，可快速更新
5. 环的处理：找到 $4$ 元环，枚举翻转组合