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

Sources：K - 小 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​Keywords：数学，思维(签到题)Solution：考虑取模的进制本质。在三进制情形下对 3 n − 1 3^{n-1} 3n−1取模，本质上为取其长度为 n n n 的后缀。由于 i , j i,j i,j 一定与 n 1 , n 2 n_1,n_2 n1​,n2​ 等长，因此仅需检查 i , j i,j i,j 首数字是否为 1 1 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; }