CF1644D题解

· · 题解

题解思路：

我们就倒着考虑，那么题目就变成了：

每次选一行一列，然后染成一个颜色，后染的色不会覆盖原来染得颜色。

那么当一个颜色会有颜色，当且仅当他是满足没有全覆盖并且行没有完全覆盖或列没有完全覆盖；

那么我们定义两个数组一个表示当前行是否完全覆盖，另一个表示当前列是否完全覆盖。

那么我们就顺着做一遍，在用两个变量分别表示覆盖了多少行和覆盖了多少列。

那么只要行数等于 n 了或者列数等于 m 了就退出或者跳过。

十年OI一场空，不开longlong见祖宗。

AC CODE：

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005, mod = 998244353;
int n, m, k, q;
int x[N], y[N];
int fn[N], fm[N];
int main()
{
    int T = 1;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d%d", &n, &m, &k, &q);
        for (int i = 1; i <= q; i++)
            scanf("%d%d", &x[i], &y[i]);
        int cn = 0, cm = 0;
        long long res = 1;
        for (int i = q; i >= 1; i--)
        {
            if (cn == n || cm == m)//若全覆盖就跳过，但最好直接跳出
                continue;
            int fl = 1;
            if (!fn[x[i]])//若没有覆盖就覆盖
                cn++, fn[x[i]] = 1, fl = k;
            if (!fm[y[i]])//同理
                cm++, fm[y[i]] = 1, fl = k;
            res = res * fl % mod;//统计答案
        }
        for (int i = q; i >= 1; i--)
            fn[x[i]] = fm[y[i]] = 0;//多组数据清空
        printf("%d\n", res);
    }
    return 0;
}