CF竞赛题目讲解_CF1758E(组合数学)
2022-12-10 09:53 作者:Clayton_Zhou | 我要投稿
AC代码
https://codeforces.com/contest/1758/submission/184430493
题意:
Tannhaus 制造了一种神秘的时钟,
由一个n×m的时钟网格组成,每个时钟总是精确地显示某个小时
(也就是说,它不在两个小时之间)。
在一次移动中,他可以选择任何行或列,并将该行或列中的所有时钟向前移动一小时†。
如果可以使所有时钟显示相同的时间,则时钟网格称为可解。
在构建自己的谜题时,坦浩斯突然担心可能无法使得网格可解。
网格中的一些单元格的时钟已经显示了某个初始时间,而其余单元格是空的。
给定部分完成的时钟网格,找出在空单元格中分配时钟的方法,以便网格可解。
答案可能是巨大的,所以答案模10^9+7。
†如果时钟当前显示小时t并向前移动一小时,则时钟将显示小时(t+1)mod h。
‡如果存在时钟在两种排列中显示不同时间的某个单元,则两种分配不同。
题解:
组合数学
通过一次修改一列,修改其他行,使得其他行一行数值相同。
最终修改都同步到第一行,如果第一行数值相同,则是可解的。