luogu#P10035. 「FAOI-R2」Paint (A)
「FAOI-R2」Paint (A)
题目背景
小 Y 是一个胖子,他最爱下楼梯了,因为下楼梯很省力气,但是他却有强迫症。
由于刷漆工人 HG 的油漆不够,每一层台阶都只刷了一半——左边或右边,好让小 Y 下楼时不踩到油漆。(众人:这是什么逻辑?)
题目描述
整个楼梯共 级台阶。
HG 刷漆的规律是:对于从上到下第 级台阶,若 是奇数,则刷在左边,否则刷在右边。 的定义请见提示。
小 Y 因为强迫症,要求自己不能踩到油漆。
现在他来求助你,他最少会踩到油漆多少次?
- 一次只能下一级台阶。
- 如果小 Y 站在当前台阶的左边,则他必须站在下一级台阶的右边,反之亦然。
- 如果油漆在当前台阶左边,那么需要站在当前台阶右边才算没踩到油漆,反之亦然。
- 小 Y 唯一可以控制的是:他在第 级台阶上站在哪边。也就是说,小 Y 只有 种下楼梯的方案供选择。
答案对 取模。
形式化题意
给定三个 01 串 ,长度均为 。字符串下标从 开始。
其中:
- ;
- ;
- ;具体来说,第 个字符为 。 的定义请见提示。
记 为字符串 和 中匹配的字符的个数。
试求:
$$\min\{\operatorname{mc}(A,C),\operatorname{mc}(B,C)\} $$答案对 取模。
输入格式
本题有多组数据。
第一行,一个正整数 ,代表数据组数。
下面 行,每行一个正整数 。
输出格式
每组数据一行,输出踩到油漆的最少次数,即 $\min\{\operatorname{mc}(A,C),\operatorname{mc}(B,C)\}$。
答案对 取模。
1
1
1
3
494699
494699494699
494699494699494699
994161775
899186285
348815909
提示
样例 解释:
- ;
- ;
- ;
- ;
- ;
- $\min\{\operatorname{mc}(A,C),\operatorname{mc}(B,C)\}=1$。
测试点编号 | 分值 | ||
---|---|---|---|
对于 的数据,,。
提示: 指 中质因数 的个数。例如,,。