#P18957. [SEUSA2026] A. 递归图案(Recursive Pattern)

[SEUSA2026] A. 递归图案(Recursive Pattern)

递归图案(Recursive Pattern)

题目描述

一个最简单的递归图案是任意一个 2×22\times2 方阵,每个格子是 X 或小写字母 o。

一个最简单的递归图案

图 A.1:一个基本递归图案。

你可以对已有图案进行扩展:任选一个新的 2×22\times2 方阵,把已有图案中的每个 X 替换为这个新方阵,把每个 o 替换为全是 o 的 2×22\times2 方阵。扩展后,图案的行数和列数都翻倍。

一次扩展的过程

图 A.2:用左侧的 2×22\times2 方阵替换已有图案中的每个 X;已有的 o 被替换为全 o 的方阵,得到右侧的 4×44\times4 图案。

可以扩展任意多次。每次选择的 2×22\times2 方阵可以不同,但同一次扩展对所有 X 使用相同的方阵。

给定一个由 X、o 组成的矩形网格,判断它是否能作为某个递归图案中的一个连续子矩形。子矩形的位置不必与任一层的分块边界对齐。

输入格式

第一行两个正整数 r,cr,c,满足 1≤rc≤2×1051\le rc\le2\times10^5。

随后 rr 行,每行 cc 个字符,只包含 X 和 o。

输出格式

若存在符合要求的递归图案,输出 1;否则输出 0。

样例

2 2
XX
Xo
1
2 3
oXo
Xoo
1
6 45
ooXXXooXooXXXXooooXXXooXXXooXoooXoXXXXoXooXoo
ooXooXoXoXXooooooXXoooXooXXoXoooXooXoooXooXoo
ooXXXooXoXooooooooXoooXoooXoXoooXooXoooXooXoo
ooXoXXoXoXooXXoooooXooXoooXoXoooXooXoooXXXXoo
ooXooXoXoXXooXoooooXXoXooXXoXXooXooXoooXooXoo
ooXXXooXooXXXXoooXXXoooXXXoooXXXoooXoooXooXoo
0

来源

2026 ICPC Southeast USA Regional Programming Contest Division 1,题目 A。

官方资料页 · 原题。中文根据用户提供的官方题面重新整理;全部测试数据来自赛事官方公开的数据包。