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

· · 题解

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

思路

在三进制情形下对 3^{n-1} 取模，本质上为取其长度为 n 的后缀。由于 i,j 一定与 n_1,n_2 等长，因此仅需检查 i,j 首数字是否为 1 即可。由于矩阵本身即为递归构造，因此天然适合递归实现，也可采用递推实现，下面采取递推实现。

AC代码

#include<bits/stdc++.h>
//Made by Stick_Man_
using namespace std;
#define int 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;
    }
}
signed main(){
    cin>>n>>n1>>n2;
    cout<<solve()<<'\n';
    return 0;
}