原题链接

题解

设想每一个 \(x,y\) 代表中控台，中控台颜色改变它控制的颜色也会跟着改变，我们倒过来求，这样就能确保每个中控台有没有控制的颜色

code

#define ll long long
#include<bits/stdc++.h>
using namespace std;
const ll mod=998244353;
ll xs[200005]={0};
ll ys[200005]={0};
ll usex[200005]={0},usey[200005]={0};

inline void read(ll &x) {
    x = 0;
    ll flag = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    x *= flag;
}

inline void write(ll x)
{
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

ll qpow(ll a, ll x)
{
    ll sum=1;
    while(x)
    {
        if(x&1) sum=sum*a%mod;
        a=a*a%mod;
        x>>=1;
    }
    return sum%mod;
}

int main()
{
    ll t;
    read(t);
    while(t--)
    {
        ll n,m,k,q;
        read(n); read(m); read(k); read(q);

        for(ll i=1;i<=q;i++) read(xs[i]), read(ys[i]);
		memset(usex,0,sizeof(usex));
		memset(usey,0,sizeof(usey));

        ll cntx=0,cnty=0,color=0;
        for(ll i=q;i>=1;i--)
        {
            ll x=xs[i],y=ys[i];

            ll con=0;
            if(!usex[x])
            {
                usex[x]=1;
                cntx++;
                con=1;
            }
            if(!usey[y])
            {
                usey[y]=1;
                cnty++;
                con=1;
            }

            color+=con;
            if(cnty>=m||cntx>=n) break;
        }
        write(qpow(k,color));
        putchar('\n');
    }
    return 0;
}