P9326 Palindromic Poster 题解
ARIS0_0
·
·
题解
（upd on 2025.1.20，修改了部分特殊点的做法。）
1. 题目解释
求一个有 r 行回文字符串和 c 列回文字符串的 n\times m 字符矩阵。
2. 思路
（一道规律题让我调吐了）
考虑对 r，c 分类讨论。
Part 1
当 r=0,c=0 时。
只需有 a_{i,j} 等于第 (i+j-1)\bmod26 个字母即可，证明比较显然。
举例：n=3,m=4,r=0,c=0。
abcd
bcde
cdef
Part 2
当 r=0,c=m 时。
只需有 a_{i,j} 等于第 i 个字母即可，证明也不难。
举例：n=3,m=4,r=0,c=4。
abcd
abcd
abcd
Part 3
当 r=0,0<c<m 时。
不难想到将 Part 1 的前 c 列填充同一字母，其余与 Part 1 相同。
举例：n=3,m=4,r=0,c=2。
abcd
abde
abef
Part 4
当 r=n,c=0 时。
与 Part 2 原理相同，只是 n 和 m 互换，r 和 c 互换。
举例：n=3,m=4,r=3,c=0。
aaaa
bbbb
cccc
Part 5
当 r=n,c=m 时。
只需填充同一种字符即可。
举例：n=3,r=4,r=3,c=4。
aaaa
aaaa
aaaa
Part 6
当 r=n,0<c<m 时。
首先考虑不不合法的情况。
先给结论：当 2\mid m,2\nmid c 时不合法，原因待会再说。
给出其余情况的构造方式：
当 2\mid m,2\mid c 时，将 1 至 \dfrac{c}{2} 列与 m-\dfrac{c}{2}+1 至 m 列的字符全部赋为 a，将 2 至 n 行的字符全部赋为 a，其余赋为 b。
举例：n=3,m=4,r=3,c=2。
abba
aaaa
aaaa
当 2\nmid m,2\mid c 时同理（只是 \dfrac{c}{2} 变为 \dfrac{c-1}{2}）。
举例：n=3,m=3,r=3,c=2。
aba
aaa
aaa
当 2\nmid m,2\nmid c 时只需将最中间一列赋为 a 也就一样了。
举例：n=3,m=3,r=3,c=1。
bab
aaa
aaa
最后解释不合法构造的原因：由于 2\mid m,2\nmid c，故而我们需要将 c 列赋为 a，而一行的字符数量为偶数，假如它是回文的，那么 a 的数量也应该是偶数个，又 2\nmid c，因而不合法。
Part 7
当 0<r<n,c=0 时。
与 Part 3 原理相同。
Part 8
当 0<r<n,c=m 时。
与 Part 6 原理相同。
Part 9
当 0<r<n,0<c<m 时。
只需将前 r 行和前 c 列的字符全部赋为 a，其余赋为 b 即可。
举例：n=3,m=4,r=1,c=2。
aaaa
aabb
aabb
Part 10
对于 n 或 m 等于 2 时的一个特殊情况补充。
另外感谢 @tyr_04 帮忙指出。
当 n=2,c=0,r\ge26 时，使用上面的方法会出现如下情况：
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bcedfghijklmnopqrstuvwxyzabcde
注意到第 26 列有两个 a。
于是我们将下方修改为第 (i-1)\bmod25+2 个字母即可。
代码不放了，其实不难写。