[POI 2021/2022 R1] Druk

Luogu
IDLGP9417
Time1000ms
Memory256MB
DifficultyP6
贪心POI(波兰)2021Ad-hoc
给你一个 $n\times m$ 的字符矩形,只含小写英文字母。 你需要制作两块模板,一个是横的(一行 $l$ 列),一个是竖的($l$ 行一列),$l$ 称为模板长度,上面有完全相同的字符串(从左到右,从上到下,不可翻转)。你需要保证你可以用这两块模板不重不漏地印刷这个字符矩形。 模板的制作方案可能有很多,你只需要输出所有的可行的模板长度即可。 ## Input 第一行两个正整数 $n,m$,表示矩形大小。 接下来是一个 $n$ 行 $m$ 列的字符矩形,只含小写英文字母。 ## Output 第一行一个整数,表示你找到的可行长度的个数。 第二行若干个整数,你找到的所有可行长度。 [samples] ## Background 译自 [XXIX Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi29-1/dashboard/) [Druk](https://sio2.mimuw.edu.pl/c/oi29-1/p/dru/)。 ## Note 样例一解释:![图挂了](https://cdn.luogu.com.cn/upload/image_hosting/2zs08vop.png) 样例四解释:![图挂了](https://cdn.luogu.com.cn/upload/image_hosting/p1zo7v6x.png) 对于所有数据,$1\leq n,m\leq 1000$。 | 子任务编号 | 附加限制 | 分数 | | :----------: | :----------: | :----------: | | 1 | $n=1,m\leq 1000$ | 10 | | 2 | $n\leq 3,m\leq 1000$ | 25 | | 3 | $n,m\leq 20$ | 20 | | 4 | | 45 |
Samples
Input #1
5 8
aabaaaaa
babaabbb
aabaaaaa
aabaaaaa
abaaabaa
Output #1
1
4
Input #2
1 1000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Output #2
16
1 2 4 5 8 10 20 25 40 50 100 125 200 250 500 1000
Input #3
3 1000
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab
Output #3
12
2 4 8 10 20 40 50 100 200 250 500 1000
Input #4
4 9
aabaaabaa
babababab
aabaaabaa
abaabaaba
Output #4
1
3
Input #5
见附件
Output #5
0

Input #6
见附件
Output #6
1
4
API Response (JSON)
{
  "problem": {
    "name": "[POI 2021/2022 R1] Druk",
    "description": {
      "content": "给你一个 $n\\times m$ 的字符矩形,只含小写英文字母。 你需要制作两块模板,一个是横的(一行 $l$ 列),一个是竖的($l$ 行一列),$l$ 称为模板长度,上面有完全相同的字符串(从左到右,从上到下,不可翻转)。你需要保证你可以用这两块模板不重不漏地印刷这个字符矩形。 模板的制作方案可能有很多,你只需要输出所有的可行的模板长度即可。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9417"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给你一个 $n\\times m$ 的字符矩形,只含小写英文字母。\n\n你需要制作两块模板,一个是横的(一行 $l$ 列),一个是竖的($l$ 行一列),$l$ 称为模板长度,上面有完全相同的字符串(从左到右,从上到下,不可翻转)。你需要保证你可以用这两块模板不重不漏地印刷这个字符矩形。\n\n模板的制作方案可能有很多,你只需要输出所有的可行的模板长度即可。\n\n## Input\n\n第一行两个正整数 $n,...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments