var code = "06ab93f6-fe92-43f7-a526-bcdcff43009f"

• 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{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\le j<2\times 3^{n-1}\0,\kern143pt \text{otherwise} \end{cases}$$
• 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;
}