真-资源勘察
测试数据来自 system/1664
背景
按照出题者原来的意思,需要求出所有的答案,但是输出太大,比赛时改成求和降低了题目的难度,所以开了此题改为xor。
描述
教主要带领一群Orzer到一个雄奇地方勘察资源。
这个地方可以用一个n×m的矩阵A[i, j]来描述,而教主所在的位置则是位于矩阵的第1行第1列。
矩阵的每一个元素A[i, j]均为一个不超过n×m的正整数,描述了位于这个位置资源的类型为第A[i, j]类。教主准备选择一个子矩阵作为勘察的范围,矩阵的左上角即为教主所在的(1, 1)。若某类资源k在教主勘察的范围内恰好出现一次。或者说若教主选择了(x, y)即第x行第y列作为子矩阵的右下角,那么在这个子矩阵中只有一个A[i, j](1≤i≤x,1≤j≤y)满足A[i, j]=k,那么第k类资源则被教主认为是稀有资源。
现在问题是,对于所有的(x, y),询问若(x, y)作为子矩阵的右下角,会有多少类不同的资源被教主认为是稀有资源。
格式
输入格式
输入的第一行包括两个正整数n和m,接下来n行,每行m个数字,描述了A[i, j]这个矩阵。
输出格式
为了照顾Vijos脑残的输出问题,设B[i, j]表示仅包含前i行与前j列的子矩阵有多少个数字恰好出现一次,那么你所要输出所有B[i, j]xor之后的结果。
样例1
样例输入1
2 3
1 2 3
3 1 2
样例输出1
0
限制
对于10%的数据,有N,M≤10;
对于20%的数据,有N,M≤20;
对于40%的数据,有N,M≤150;
对于50%的数据,A[I, J]≤1000;
对于70%的数据,有N,M≤800;
对于100%的数据,有N,M≤1000,A[I, J] ≤N×M。
时限1s。
提示
对于右下角为(1,1)的子矩阵,仅包含数字1,所以答案为1。
对于右下角为(1,2)的子矩阵,数字1、2各出现一次,所以答案为2。
对于右下角为(1,3)的子矩阵,数字1、2、3各出现一次,所以答案为3。
对于右下角为(2,1)的子矩阵,数字1、3各出现一次,所以答案为2。
对于右下角为(2,2)的子矩阵,数字2、3各出现一次,但是数字1出现了两次,所以数字1不统计入答案,答案为2。
对于右下角为(2,3)的子矩阵,数字1、2、3均出现了两次,所以答案为0。
所以结果为1 xor 2 xor 3 xor 2 xor 2 xor 0=0。
信息
- ID
- 1612
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者