自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 22:54:04，当前版本为作者最后更新于2022-08-07 18:10:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这个题目是一个数学题，打表可以发现答案是……

好了，言归正传。

下文设 $X_K$ 为字符串 $X$ 在 $N=K$ 时的值，字符串间的 $+$ 为 C++/STL/string 中的字符串拼接。

设 $A_N$ 和 $B_N$ 中与 $C_N$ 匹配次数较少的字符串为 $G_N$（另一个为 $H_N$），则 $\operatorname{mc}(G_{N},C_{N})=\dfrac{3^N-1}{2}$，且 $G_N$ 和 $C_N$ 的最后一位一定不同。

证明：

首先，$N=1$ 时显然成立，即样例 $1$。

接下来，从 $N$ 推到 $N+1$：

下面的性质很显然，证明不给了。

$A_{N+1}=A_N+B_N+A_N$；

$B_{N+1}=B_N+A_N+B_N$；

$C_{N+1}=C_N+C_N+D_N$（$D_N$ 是 $C_N$ 改变最后一位，即 $\texttt{1}$ 变成 $\texttt{0}$，$\texttt{0}$ 变成 $\texttt{1}$ 后的字符串）。

可以发现，此时 $\operatorname{mc}(A_{N+1},C_{N+1})=\operatorname{mc}(A_{N},C_{N})+\operatorname{mc}(B_{N},C_{N})+\operatorname{mc}(A_{N},D_{N})$，$\operatorname{mc}(B_{N+1},C_{N+1})=\operatorname{mc}(B_{N},C_{N})+\operatorname{mc}(A_{N},C_{N})+\operatorname{mc}(B_{N},D_{N})$。

若 $\operatorname{mc}(G_{N},C_{N})=\dfrac{3^N-1}{2}$，且 $G_N$ 和 $C_N$ 的最后一位不同，则 $\operatorname{mc}(G_{N},D_{N})=\dfrac{3^N+1}{2}$。

而由于当 $G_N$ 与 $H_N$ 「合在一起」（每个位置两个字符）时，每位各出现了一个 $\texttt{0}$ 和一个 $\texttt{1}$（必有一个和 $D_N$ 对应位置匹配），因此 $\operatorname{mc}(G_{N},D_{N})+\operatorname{mc}(H_{N},D_{N})=3^N$。

也就是说，$\operatorname{mc}(H_{N},D_{N})=\dfrac{3^N-1}{2}$。

它们之间差 $1$，因此 $\operatorname{mc}(A_{N+1},C_{N+1})$ 与 $\operatorname{mc}(B_{N+1},C_{N+1})$ 之间也差 $1$（其余的抵消了）。

同理，$\operatorname{mc}(G_{N+1},C_{N+1})+\operatorname{mc}(H_{N+1},C_{N+1})=3^{N+1}$。

因此，$\operatorname{mc}(G_{N+1},C_{N+1})=\dfrac{3^{N+1}-1}{2}$（列方程组可得）。

此外，由于 $\operatorname{mc}(H_{N},D_{N})<\operatorname{mc}(G_{N},D_{N})$，因此 $\operatorname{mc}(G_{N+1},C_{N+1})$ 的展开式（指「可以发现」那一句中的公式）中的最后一项是 $\operatorname{mc}(H_{N},D_{N})$。

而由于 $D_N$ 与 $C_N$，$C_N$ 与 $G_N$，$G_N$ 与 $H_N$ 的最后一位都不同，因此 $D_N$ 与 $H_N$ 的最后一位也不同，即 $G_{N+1}$ 与 $C_{N+1}$ 的最后一位也不同。

根据数学归纳法，得证。

也就是说，答案就是 $\dfrac{3^N-1}{2}$！

std：

#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;
}