P10035 「FAOI-R2」Paint

题目背景

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

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

题目描述

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

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

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

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

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

答案对 $10^9+7$ 取模。

形式化题意

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

其中：

• $A=\text{101010101…101}$；
• $B=\text{010101010…010}$；
• $C=\text{001001000…}$；具体来说，第 $I$ 个字符为 $V_3(I)\mathrm{mod}2$。$V_3(I)$ 的定义请见提示。

记 $\mathrm{mc}(X,Y)$ 为字符串 $X$ 和 $Y$ 中匹配的字符的个数。

试求：

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

答案对 $10^9+7$ 取模。

输入格式

本题有多组数据。

第一行，一个正整数 $T$，代表数据组数。

下面 $T$ 行，每行一个正整数 $N$。

输出格式

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

答案对 $10^9+7$ 取模。

输入输出样例 #1

输入 #1

1
1

输出 #1

1

输入输出样例 #2

输入 #2

3
494699
494699494699
494699494699494699

输出 #2

994161775
899186285
348815909

说明/提示

样例 $1$ 解释：

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

---

测试点编号	$T\le$	$N\le$	分值
$1$	$10$	$10$	$50$
$2$	$10^5$	$10^{18}$	$50$

对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le N\le 10^{18}$。

提示： $V_3(X)$ 指 $X$ 中质因数 $3$ 的个数。例如，$V_3(14)=0$，$V_3(18)=2$。

C++实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
	return x * f;
}
const ll mod = 1000000007;
ll T;
inline ll power(ll a, ll b) {
	ll ans = 1;
	while(b) {
		if(b & 1) ans = (ans * a) % mod;
		a = (a * a) % mod;
		b >>= 1;
	}
	return ans;
}
signed main() {
    T = read();
    while(T--) {
        ll x = read(); x %= mod - 1;
        ll a = power(3, x) - 1;
        printf("%lld\n", ((a & 1) ? a + mod : a) / 2);
    }
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容