AT_arc193_c Grid Coloring 3 题解

为什么我会在凌晨一点钟写这个题解。

非常好题目！

考察什么图案是合法的。

首先你注意到对于每行每列，我们只需要保留最后一次在这一行或列的元素即可。

不妨给每个行/列都钦定一个优先级，优先级底的在上面，这样每个格子的颜色就是行和列中优先级较低的那个对应的颜色。考虑一组优先级何时可以实现。

首先，最上面一层一定是一个十字。这意味着一定有一行一列优先级都是 。这个显然是必要的。然后你发现，这个也是充分的。

因为，假设你要单独覆盖一行，你只需要在顶层十字覆盖的那一列选择对应行的格子即可。列同理。

因此，要生成一个图案，我们首先必须要找一个十字填上，然后对于剩下的格子，你可以删掉一行同色元素或者删掉一列同色的元素，如果能删完，那么就是可行的。

不过问题在于，一个图案的生成方式不唯一。因此我们不能直接对删除方式计数。

不妨倒着考虑，每次加入一行或者一列。

考虑 表示大小为 的举行，用 种不同的颜色，每次加入一行或者一列能生成的不同的不重不漏的图案个数。

考虑如何转移。我们有两种选择。

  • 加入一行。有 种选择行的方式， 种选择颜色的方式。。
  • 加入一列。有 种选择列的方式， 种选择颜色的方式。。

但是这个转移是有问题的。我们考虑什么时候会出问题。

有三种情况。

  • 存在多个相同颜色的行（这些行之间的颜色不一定相同）。此时任选其中一个行作为新加入的行都会被计算一次。
  • 存在多个相同颜色的列（这些列之间的颜色不一定相同）。此时任选其中一个列作为新加入的列都会被计算一次。
  • 存在多个同色十字。此时选择十字中的行或者列都会被计算一次。

我们可以考虑容斥。

我们可以枚举一个 ，表示钦定新图案中若干个行作为新加入的行，其方案数就是 。

枚举一个列，表示钦定最终图案中若干个列作为新加入的列，方案数是 。

我们考虑对于上面两个计算方式，上面三个可能出问题的情况会被计算多少次。就是下面这个表格。

钦定 行 钦定 列
实际有 个同色的行
实际有 个同色的列
实际有 个同色十字

我们希望三个中的每一个都只做 的贡献。

先考虑前两个的情况。实际有 个同色行的图案，其被计算的次数是

其中 为钦定 个行的容斥系数。

不难发现此时取 即可让每个图案都做 的贡献。这是因为同一行组合数的奇数位置之和和偶数位置之和是相等的，把 移动到右侧就是这个式子。

对于列也类似的做一个容斥即可。此时你在看一下这个表格。

钦定 行 钦定 列
实际有 个同色的行
实际有 个同色的列
实际有 个同色十字

我们发现还有一个问题，就是有十字的情况被算了 遍。我们需要减掉这部分。

钦定 行 列作为同色十字。方案数是 。意义是先选出来这些行和列，然后有 种选择颜色的方式。

假设实际上有 的同色十字。那么实际上被计算的次数是 。

换句话说，令 表示前好有 同色十字的方案数， 表示钦定 同色十字的方案数。

我们有

我们希望求出来

你猜一下容斥系数为 。然后发现就对了。

因为

然后右边一坨内层 求和之后是 ，外层 求和也是 。

然后你直接这样做就可以了。复杂度 。但是并过不了。

注意到复杂度瓶颈在于十字的计算。

也就是这个东西。

其中一部分只和 有关，另一部分只和 有关，我们分离一下。

对于每个 ，预处理

这样在枚举 的时候，我们就能用 的复杂度计算这个式子了。

总共的复杂度就是 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
#include <iostream>
#include <vector>

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

#if 0
#include <fstream>

std::ifstream fin("gridcolor.in");
std::ofstream fout("gridcolor.out");
#else
#include <iostream>

std::istream &fin = std::cin;
std::ostream &fout = std::cout;
#endif

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;
    }
};

using modint998244353 = modular<998244353>;
using modint1000000007 = modular<1000000007>;
} // 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 {
constexpr bool is_prime(const ull &x) {
    for (size_t i = 2; i * i <= x; i++) {
        if (x % i) {
            continue;
        }
        return false;
    }
    return true;
}

template <ull MOD>
struct combine {
    static_assert(is_prime(MOD));

    using mll = maths::modular<MOD>;

    mll inv(const mll &x) const {
        static_assert(is_prime(MOD));
        return maths::quick_pow<mll>(x, MOD - 2, 1);
    }

    mll factrial(uint n) const {
        static std::vector<mll> fact{1};
        for (size_t i = fact.size(); i <= n; i++) {
            fact.push_back(fact.back() * i);
        }

        return fact[n];
    }

    mll factrial_inv(uint n) const {
        static std::vector<mll> inv_fact{1};
        for (size_t i = inv_fact.size(); i <= n; i++) {
            inv_fact.push_back(inv(i) * inv_fact.back());
        }

        return inv_fact[n];
    }

    mll operator()(int n, int m) const {
        if (n < 0 || m > n) {
            return 0;
        }
        else {
            return factrial(n) * factrial_inv(m) * factrial_inv(n - m);
        }
    }
};
} // namespace maths

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

const maths::combine<MOD> cmb;

void solve() {
    uint n, m, c;
    fin >> n >> m >> c;

    std::vector<std::vector<mll>> dp(n, std::vector<mll>(m));

    for (size_t i = 0; i < n; i++) {
        dp[i][0] = 1;
    }

    for (size_t j = 0; j < m; j++) {
        dp[0][j] = 1;
    }

    auto cross = [&](uint x, uint y) {
        mll ret = 0;
        for (size_t i = 0; i < x; i++) {
            mll cur = 0;
            for (size_t j = 0; j < y; j++) {
                uint cx = i, cy = y - j;

                cur += cmb(y, j) * (cx & 1 ? -1 : 1) * (cy & 1 ? -1 : 1) *
                       dp[i][j];
            }
            ret += cmb(x, i) * cur * (x & 1 ? -1 : 1);
        }

        return ret * c;
    };

    for (size_t x = 1; x < n; x++) {
        std::vector<mll> sum(m);

        for (size_t j = 0; j < m; j++) {
            for (size_t i = 0; i < x; i++) {
                sum[j] += cmb(x, i) * dp[i][j] * ((x - i) & 1 ? -1 : 1) *
                          (j & 1 ? -1 : 1);
            }
        }

        auto fetch = [&](uint y) {
            mll ret = 0;
            for (size_t j = 0; j < y; j++) {
                ret += cmb(y, j) * sum[j];
            }
            return ret * (y & 1 ? -1 : 1) * c;
        };

        for (size_t j = 1; j < m; j++) {
            for (size_t dx = 0; dx < x; dx++) {
                dp[x][j] += ((x - dx) & 1 ? 1 : -1) * dp[dx][j] *
                            maths::quick_pow<mll>(c, x - dx, 1) * cmb(x, dx);
            }

            for (size_t dy = 0; dy < j; dy++) {
                dp[x][j] += ((j - dy) & 1 ? 1 : -1) * dp[x][dy] *
                            maths::quick_pow<mll>(c, j - dy, 1) * cmb(j, dy);
            }

            dp[x][j] -= fetch(j);
        }
    }

    fout << cross(n, m) << "\n";
}
} // namespace solve

int main() {
    solve::solve();
    fout << std::flush;
}

OI > 题解
AT_arc193_c Grid Coloring 3 题解
https://blogs.sving1024.top/posts/39288/
发布于
2026年9月2日
许可协议