欢迎光临散文网 会员登陆 & 注册

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。

‡如果存在时钟在两种排列中显示不同时间的某个单元,则两种分配不同。


题解:

组合数学


通过一次修改一列,修改其他行,使得其他行一行数值相同。

最终修改都同步到第一行,如果第一行数值相同,则是可解的。


CF竞赛题目讲解_CF1758E(组合数学)的评论 (共 条)

分享到微博请遵守国家法律