[题解]2024CCPC重庆站-小 C 的神秘图形
Abstract：给定正整数
n
(
1
≤
n
≤
1
0
5
)
n(1\le n\le 10^5)
n(1≤n≤105)，三进制字符串
n
1
,
n
2
(
∣
n
1
∣
=
∣
n
2
∣
=
n
)
n_1,n_2(|n_1|=|n_2|=n)
n1,n2(∣n1∣=∣n2∣=n)，按如下方法构造
3
n
3^n
3n 阶
0
/
1
0/1
0/1 方阵
A
n
A_n
An(行列编号均从
0
0
0 开始)，回答
A
n
(
n
1
,
n
2
)
A_n(n_1,n_2)
An(n1,n2)的值：
A
n
(
i
,
j
)
=
{
1
,
n
=
1
A
n
−
1
(
i
m
o
d
3
n
−
1
,
j
m
o
d
3
n
−
1
)
,
n
≥
2
}
若
3
n
−
1
≤
i
<
2
×
3
n
−
1
,
或
3
n
−
1
≤
j
<
2
×
3
n
−
1
0
,
otherwise
A_n(i,j)=\begin{cases}\begin{rcases}1, & n=1\\ A_{n-1}(i \mod 3^{n-1},j\mod 3^{n-1}),& n\ge2\end{rcases}若3^{n-1}\le i<2\times 3^{n-1},或3^{n-1}\le j<2\times 3^{n-1}\\0,\kern143pt \text{otherwise} \end{cases}
An(i,j)=⎩
⎨
⎧1,An−1(imod3n−1,jmod3n−1),n=1n≥2}若3n−1≤i<2×3n−1,或3n−1≤j<2×3n−10,otherwise