[题解]2024CCPC重庆站-小 C 的神秘图形

• Sources：K - 小 C 的神秘图形
• Abstract：给定正整数 $n(1\le n\le 10^5)$，三进制字符串 $n_1,n_2(|n_1|=|n_2|=n)$，按如下方法构造 $3^n$ 阶 $0/1$ 方阵 $A_n$(行列编号均从 $0$ 开始)，回答$A_n(n_1,n_2)$的值：$$A_n(i,j)=\{\begin{array}{l}\begin{array}{ll}1,& n=1\\ A_{n-1}(i\mathrm{mod}{3}^{n-1},j\mathrm{mod}{3}^{n-1}),& n\ge 2\end{array}\}若3^{n-1}\le i<2\times 3^{n-1},或3^{n-1}\le j<2\times 3^{n-1}\\ 0,\text{otherwise}\end{array}$$
• Keywords：数学，思维(签到题)
• Solution：考虑取模的进制本质。在三进制情形下对$3^{n-1}$取模，本质上为取其长度为 $n$ 的后缀。由于 $i,j$ 一定与 $n_1,n_2$ 等长，因此仅需检查 $i,j$ 首数字是否为 $1$ 即可。由于矩阵本身即为递归构造，因此天然适合递归实现，也可采用递推实现。下面采取递推实现。
• Code：

#include<bits/stdc++.h>using namespace std;
using ll=long long;int n;
string n1,n2;int solve(){for(int i=0;i<n;){if(n1[i]=='1'||n2[i]=='1'){if(i==n-1) return 1;else i++;}else return 0;}
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>n1>>n2;cout<<solve()<<'\n';return 0;
}