luogu#P10035. 「FAOI-R2」Paint (A)

「FAOI-R2」Paint (A)

题目背景

小 Y 是一个胖子,他最爱下楼梯了,因为下楼梯很省力气,但是他却有强迫症。

由于刷漆工人 HG 的油漆不够,每一层台阶都只刷了一半——左边或右边,好让小 Y 下楼时不踩到油漆。(众人:这是什么逻辑?

题目描述

整个楼梯共 3N3^N 级台阶。

HG 刷漆的规律是:对于从上到下II 级台阶,若 V3(I)V_3(I) 是奇数,则刷在左边,否则刷在右边。V3(I)V_3(I) 的定义请见提示。

小 Y 因为强迫症,要求自己不能踩到油漆。

现在他来求助你,他最少会踩到油漆多少次?

  • 一次只能下一级台阶。
  • 如果小 Y 站在当前台阶的左边,则他必须站在下一级台阶的右边,反之亦然。
  • 如果油漆在当前台阶左边,那么需要站在当前台阶右边才算没踩到油漆,反之亦然。
  • 小 Y 唯一可以控制的是:他在第 11 级台阶上站在哪边。也就是说,小 Y 只有 22 种下楼梯的方案供选择。

答案对 109+710^9+7 取模。

形式化题意

给定三个 01 串 A,B,CA,B,C,长度均为 3N3^N。字符串下标从 11 开始。

其中:

  • A=101010101101A=\texttt{101010101\ldots101}
  • B=010101010010B=\texttt{010101010\ldots010}
  • C=001001000C=\texttt{001001000\ldots};具体来说,第 II 个字符为 V3(I)mod2V_3(I) \bmod 2V3(I)V_3(I) 的定义请见提示。

mc(X,Y)\operatorname{mc}(X,Y) 为字符串 XXYY 中匹配的字符的个数。

试求:

$$\min\{\operatorname{mc}(A,C),\operatorname{mc}(B,C)\} $$

答案对 109+710^9+7 取模。

输入格式

本题有多组数据。

第一行,一个正整数 TT,代表数据组数。

下面 TT 行,每行一个正整数 NN

输出格式

每组数据一行,输出踩到油漆的最少次数,即 $\min\{\operatorname{mc}(A,C),\operatorname{mc}(B,C)\}$。

答案对 109+710^9+7 取模。

1
1
1
3
494699
494699494699
494699494699494699
994161775
899186285
348815909

提示

样例 11 解释:

  • A=101A=\texttt{101}
  • B=010B=\texttt{010}
  • C=001C=\texttt{001}
  • mc(A,C)=2\operatorname{mc}(A,C)=2
  • mc(B,C)=1\operatorname{mc}(B,C)=1
  • $\min\{\operatorname{mc}(A,C),\operatorname{mc}(B,C)\}=1$。

测试点编号 TT \le NN \le 分值
11 1010 5050
22 10510^5 101810^{18}

对于 100%100\% 的数据,1T1051 \le T \le 10^{5}1N10181 \le N \le 10^{18}

提示: V3(X)V_3(X)XX 中质因数 33 的个数。例如,V3(14)=0V_3(14)=0V3(18)=2V_3(18)=2