P10035 (Official)

· · 题解

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

好了，言归正传。

下文设 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：

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

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