• 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;
}