题目描述
Yazid 喜欢吃大碗宽面。现有 m 碗宽面,其中第 i 碗宽面(1≤i≤m)共包含 ni 根面条,它们的宽度分别为 Ai,1,Ai,2,⋯,Ai,n。
记 f(u,v) 表示若混合第 u 碗宽面和第 v 碗宽面,将得到的超大碗宽面的第 ⌊2nu+nv+1⌋ 小的面条宽度(⌊x⌋ 表示不超过 x 的最大整数)。
Yazid 想求出所有 f(u,v),但为了节省你的输出时间,你只需要对所有 1≤u≤m 求出:
- R(u)=v=1xorm(f(u,v)+u+v)(xor 指异或运算,在 C++ 语言中对应
^
运算符)。
输入格式
第一行一个正整数 m,表示宽面碗数。
接下来 m 行,每行若干个用单个空格隔开的整数描述一碗宽面:这部分的第 i 行的第一个正整数为 ni,表示第 i 碗宽面包含的面条数;接下来 ni 个非负整数 Ai,j 描述各面条的宽度。
输出格式
输出 n 行,每行一个整数,其中第 i 行的整数为 R(i)。
提示
样例说明
对于样例 1:
- R(1)=(f(1,1)+2)xor(f(1,2)+3)xor(f(1,3)+4)=4xor6xor6=4
- R(2)=(f(2,1)+3)xor(f(2,2)+4)xor(f(2,3)+5)=6xor8xor9=7
- R(3)=(f(3,1)+4)xor(f(3,2)+5)xor(f(3,3)+6)=6xor9xor8=7
数据规模与约定
对于 100% 的数据,m≤104,ni≤500,0≤Ai,j≤109。
说明
来自 THUPC(THU Programming Contest,清华大学程序设计竞赛)2019。
题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。