CF1644D Cross Coloring

題意:

在一個 \(n\) 行 \(m\) 列的網格裡執行 \(q\) 次操作，每次操作在 \(k\) 種顏色中 (沒有初始顏色) 選擇一種給第 \(x_i\) 行和第 \(y_i\) 列染色且覆蓋原有顏色，問最終染色方案數

做法:

因為後染的色會覆蓋先染的色，所以最後染的色一定不會被覆蓋，不需要處理被覆蓋的情況,所以我們從後向前枚舉每次操作，如果當前列和當前行都已經被染色，那麼這次操作會被後面的操作覆蓋，對結果沒有影響，不需要統計，否則共有 \(k\) 種染色方法，將答案 \(\times k\)。

特判:

當網格全部被覆蓋，即 \(n\) 行或 \(m\) 列全部被覆蓋時，前面的操作對最終結果都沒有影響,直接跳出即可。

時間複雜度 \(O(TQ)\)

記得開 long long ！

代碼:

#include<iostream>
#define int long long
using namespace std;

int T;
int a[200010], b[200010];
bool x[200010], y[200010];

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int maxx(int x, int y)
{
	return x > y ? x : y;
}

signed main()
{
	T = read();
	while(T--)
	{
		int n=read(), m=read(), k=read(), q=read();
		int xf=0, yf=0, ans=1, c=maxx(n, m);
		for(int i=1; i<=c; i++)
		{
			x[i] = y[i] = false;
		}
		for(int i=1; i<=q; i++)
		{
			a[i] = read();
			b[i] = read();
		}
		for(int i=q; i>=1; i--)
		{
			if(xf == n || yf == m)
			{
				break;
			}
			bool flag = false;
			if(x[a[i]] == false)
			{
				x[a[i]] = true;
				flag = true;
				xf ++;
			}
			if(y[b[i]] == false)
			{
				y[b[i]] = true;
				flag = true;
				yf ++;
			}
			if(flag)
			{
				ans *= k;
				ans %= 998244353;
			}
		}
		cout << ans << '\n';
	}
	return 0;
}