CF1644D Cross Coloring
题意:
在一个 \(n\) 行 \(m\) 列的网格里执行 \(q\) 次操作，每次操作在 \(k\) 种颜色中 (没有初始颜色) 选择一种给第 \(x_i\) 行和第 \(y_i\) 列染色且覆盖原有颜色，问最终染色方案数
做法:
因为后染的色会覆盖先染的色，所以最后染的色一定不会被覆盖，不需要处理被覆盖的情况,所以我们从后向前枚举每次操作，如果当前列和当前行都已经被染色，那么这次操作会被后面的操作覆盖，对结果没有影响，不需要统计，否则共有 \(k\) 种染色方法，将答案 \(\times k\)。
特判:
当网格全部被覆盖，即 \(n\) 行或 \(m\) 列全部被覆盖时，前面的操作对最终结果都没有影响,直接跳出即可。
时间复杂度 \(O(TQ)\)
记得开 long long ！
代码:
[code]#include#define int long longusing 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'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch 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 |
