D. Cross Coloring
题意
$n \times m $ 的方格纸上进行 q 次操作,每次操作选择某整行 x 和某整列 y,使得行 x 和列 y 均涂上 k 种颜色中的一种。问你最终的方案数
思路
代码
//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*
*/
const int maxm = 2e5 + 5, inf = 0x3f3f3f3f, mod = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n, m, k, q;
cin >> n >> m >> k >> q;
vector<pii> a;
for(int i = 0; i < q; ++ i){
int x, y;
cin >> x >> y;
a.push_back({x, y});
}
vector<bool> r(n + 1, false), c(m + 1, false);
ll ans = 1, sr = n, sc = m;
for(int i = a.size() - 1; i >= 0; -- i){
int u = a[i].first, v = a[i].second;
if(!r[u] || !c[v]){
bool f = false;
if(!r[u] && sc) f = true;
if(!c[v] && sr) f = true;
if(f) ans = ans * k % mod;
if(!r[u]) -- sr;
if(!c[v]) -- sc;
r[u] = c[v] = true;
}
}
cout << ans << '\n';
return ;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
cin >> _;
while(_ --){
solve();
}
return 0;
}
- Educational Codeforces 思维 Round 123educational codeforces思维round educational codeforces round rated educational codeforces multiset思维 educational codeforces思维 数学 educational codeforces round 151 construction educational codeforces round cf-educational educational codeforces round educational codeforces round 147 educational codeforces round 158 educational codeforces contest round