题解：AT_ddcc2020_qual_f DISCOSMOS

q1uple · 2026-05-10 18:01:51 · 题解

不是很难啊。难度严格小于 P4558。

套路考虑 i \to (i+T) \mod H 和 j \to (j+T) \mod W。放入一个等价类中，分别有 \gcd(H,T) 和 \gcd(W,T) 个，最后算一下就行了。不妨设 n=\dfrac{H}{\gcd(H,T)},m=\dfrac{W}{\gcd(W,T)}。考虑计算总的贡献。

• 全部都是 .，这个是一种方案。
• 不存在 v，且不全部都是 .，每一行显然只有两种情况，答案便是 2^n-1。
• 不存在 >，且不全部都是 .，每一列显然只有两种情况，答案便是 2^m-1。
• 同时存在 > 和 v，且不全部都是 . 或 >，这个根据我们上面说的，显然是没有 . 的，而且如果你做过 P4558 这个题的话，马上就能意识到 (i-1,j) 和 (i,j-1) 这两个地方一定是一样的，不然绝对不合法。按照那个题的做法我们知道对于 S=i+j，属于一个小等价类，并且不难发现一共有 \gcd(n,m) 个等价类，这个你直接列两个同余方程就行，所以答案便是 2^{\gcd(n,m)}-2。

所以总的答案是

这个就不需要给代码了吧。