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

好了，言归正传。

下文设 $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;
}

打表大法好啊：

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
int power(long long a,long long b){
    long long ans=1;
    while(b){
        if(b&1){
            ans=ans*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return ans;

}
int main(){
    int T;
    cin>>T;
    while (T--) {
        long long n;
        cin>>n;
        long long a=power(3,n)-1;
        cout<<((a & 1) ? a + mod : a) / 2<<endl;
    }
}

Solution

给一个找规律的解法。

我们可以先用程序将 $[1,5]$ 区间内所有的答案打出来，结果为：

拿 $n=4$ 举例，发现 $40 = 3 ^ 0 + 3 ^ 1 + 3 ^ 2 + 3 ^ 3$。

$\therefore$ 答案便是 $3^0+3^1+\dots+3^{n-1}$。

那如何快速求出答案呢，下面进行推导。

设 $S = 3^0+3^1+\dots+3^{n-1}$，则 $3S = 3^1+3^2+\dots+3^n$。

$\because 2S = 3S - S = (3^1+3^2+\dots+3^n) - (3^0+3^1+\dots+3^{n-1})$ $=3^{n}-1$。

$\therefore S = \dfrac{2S}{2}= \dfrac{3^{n}-1}{2}$。

推导过后，整个题目便变得明朗起来了。直接快速幂求出 $3^{n}$ 后套公式即可。