跳到主要内容
图灵 OJTURING / ONLINE JUDGE

F. [CCPC 2024 重庆站] 小 C 的神秘图形

  • 传统题
  • 1000ms
  • 512MiB

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

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

题目描述

对于正整数 nn,定义一个 3n×3n3^n\times 3^n 的 0101 矩阵 AnA_n。矩阵的行、列编号均从 00 开始,An(i,j)A_n(i,j) 表示第 ii 行、第 jj 列的元素。

令 m=3n−1m=3^{n-1}。按照以下规则定义矩阵中的每个元素:

  1. 若 ii 和 jj 均不在区间 [m,2m)[m,2m) 内,则 An(i,j)=0A_n(i,j)=0。
  2. 若 ii 或 jj 至少有一个在区间 [m,2m)[m,2m) 内,且 n=1n=1,则 An(i,j)=1A_n(i,j)=1。
  3. 若 ii 或 jj 至少有一个在区间 [m,2m)[m,2m) 内,且 n≥2n\geq 2,则 An(i,j)=An−1(i mod m,j mod m)A_n(i,j)=A_{n-1}(i\bmod m,j\bmod m)。

其中,区间 [m,2m)[m,2m) 包含 mm,不包含 2m2m;x mod mx\bmod m 表示 xx 除以 mm 后的余数。

例如,n=1n=1 时,矩阵 A1A_1 为:

0 1 0
1 1 1
0 1 0

现在,给定正整数 nn,以及两个长度为 nn 的数字串,其中每位都是 0,1,20,1,2 中的一个。它们分别表示三进制数 n1,n2n_1,n_2,可能包含前导 00。你需要求出 An(n1,n2)A_n(n_1,n_2) 的值。

输入格式

第一行输入一个正整数 n(1≤n≤105)n (1\leq n\leq 10^5),含义见题目描述。

接下来两行,每行输入一个长度为 nn 的数字串,分别表示三进制数 n1,n2n_1,n_2。

输出格式

输出一个整数,表示 An(n1,n2)A_n(n_1,n_2) 的值。

样例 1

2
20
01
0

样例 2

3
102
011
1

说明

当 n=2n=2 时,矩阵 A2A_2 为:

0 0 0 0 1 0 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 0 0
0 1 0 0 1 0 0 1 0
1 1 1 1 1 1 1 1 1
0 1 0 0 1 0 0 1 0
0 0 0 0 1 0 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 0 0

样例 1 中,三进制串 20 和 01 分别表示 n1=6,n2=1n_1=6,n_2=1,因此 A2(6,1)=0A_2(6,1)=0。

来源

原题。题意按原题整理,测试数据由本站独立构造。

思维特训

未参加
状态
已结束
规则
XCPC
题目
6
开始于
2026-10-5 19:00
结束于
2026-10-6 0:00
持续时间
5 小时
主持人
参赛人数
20