#P18338. RDDCCD
RDDCCD
RDDCCD
标准输入,标准输出。
陈教授发明了一种支持 RDDCCD(Reverse Diagonal Digits, Calculate Common Divisor,反转对角线数位并计算最大公约数)操作的数据结构。一次操作会将矩阵中某条对角线上的每一个数的十进制数位反转,然后计算整个矩阵中所有数的最大公约数。
例如,反转12345得到54321,反转2748得到8472。
这种数据结构暂时还是商业秘密。给定初始矩阵以及操作序列,请自行实现能够高效完成这些操作的程序。
矩阵的行、列编号均从1开始。用 表示第 行、第 列的数。每次操作由一个字符 和一个整数 表示:
- 若 为
+,反转所有满足 的格子中的数; - 若 为
-,反转所有满足 的格子中的数。
操作会持续改变矩阵。每次反转完成后,求当前全部 个数的最大公约数。
输入格式
第一行包含两个整数 ,分别表示方阵的边长和操作次数。
接下来 行,每行包含 个整数。第 行第 个整数为初始值 。
接下来 行,每行包含一个字符 和一个整数 ,表示第 次操作。
输出格式
输出 行,每行一个整数,表示相应操作完成后整个矩阵所有数的最大公约数。
不输出初始矩阵的最大公约数。
数据范围与保证
- ;
- ;
- ;
- 初始的每个数都不以0结尾,因此数位反转不会丢失位数;
- ,且 ;
- 每次操作至少反转一个格子中的数。
上述最后两个条件须同时满足。按1开始的行列编号,它们意味着:+ 操作的 满足 ;- 操作的 满足 。特别地, 时可用的操作是 - 0。
本题只有一组矩阵,不含测试用例数。
样例输入 1
3 5
202 4 6
8 12 21
32 44 82
+ 2
+ 5
- 0
+ 4
- 2
样例输出 1
1
2
1
1
2