台中网站建设,网站关键词优化网站推广,京东企业门户,官方网站建设网站Sources#xff1a;K - 小 C 的神秘图形Abstract#xff1a;给定正整数 n ( 1 ≤ n ≤ 1 0 5 ) n(1\le n\le 10^5) n(1≤n≤105)#xff0c;三进制字符串 n 1 , n 2 ( ∣ n 1 ∣ ∣ n 2 ∣ n ) n_1,n_2(|n_1||n_2|n) n1,n2(∣n1∣∣n2∣n)#xff0c;按如下方法…SourcesK - 小 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, n1\\ A_{n-1}(i \mod 3^{n-1},j\mod 3^{n-1}), n\ge2\end{rcases}若3^{n-1}\le i2\times 3^{n-1},或3^{n-1}\le j2\times 3^{n-1}\\0,\kern143pt \text{otherwise} \end{cases} An(i,j)⎩ ⎨ ⎧1,An−1(imod3n−1,jmod3n−1),n1n≥2}若3n−1≤i2×3n−1,或3n−1≤j2×3n−10,otherwiseKeywords数学思维(签到题)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
#includebits/stdc.husing namespace std;
using lllong long;int n;
string n1,n2;int solve(){for(int i0;in;){if(n1[i]1||n2[i]1){if(in-1) return 1;else i;}else return 0;}
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinnn1n2;coutsolve()\n;return 0;
}
