Problem - D - Codeforces

有一张纸，可以用大小为n × m的网格表示:n行和m列的单元格。所有的细胞最初都是白色的。G操作已应用于该工作表。其中的i可以描述为:2i yi-从k种非白色中选择一种，然后给整行和整列y上色。新颜色应用于每个单元格，而不管该单元格在操作之前是否被着色。应用所有q运算后的薄片称为着色。如果至少有一个单元格被着色，则两种颜色是不同的有多少种不同的颜色?打印数字模998 244 353。输入第一行包含一个整数t (1

Example

input

Copy

2

1 1 3 2

1 1

1 1

2 2 2 3

2 1

1 1

2 2

output

Copy

3
4

注意:

如果使用#define int long long 是无法通过这道题的 会T

以后输入输出都用scanf,

题解

用于涂改是按顺序的,所以一个点是什么颜色都是由最后一次在这个点上染色决定的

所以我们反过来考虑

如果点没有被染色过,不考虑

记录点最后一次被染色,可以染k种,所以乘k

如何判断一个点被染过色

1.所有行被染过 都不考虑了

2.所有列被染过 都不考虑了

3.该行该列 被染过 不考虑了

用两个数组记录行列是否被染过即可

#include
#include
#include
#include
#include
#include