P10035
FiraCode
·
·
题解
思路：
我们发现对于长度为 6 的 C，对应的 A, B 本质都是相同的。
即当 C=\texttt{001001} 时 A = \texttt{010101} 而 B = \texttt{101010}。
然后由于长度为 $3^n$，所以一共有 $3^{n-1}$ 个 $3$。由于 $3^{n-1}$ 一定为奇数，所以一共有 $\frac{3^{n-1}-1}{2}$ 个 $6$ 以及一个 $3$。
那么每个 $6$ 的贡献一定是 $3$，所以考虑多余的一个 $3$ 贡献是多少。
那么一定是 $\texttt{010}$ 贡献最少为 $1$。
然后按照上边说的写即可。
## Code:
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T;
ll n;
const int mod = 1e9 + 7;
ll power(ll a, ll b) {
ll res = 1;
for (; b; b >>= 1, a = a * a % mod)
if (b & 1) res = res * a % mod;
return res;
}
signed main(){
scanf("%d", &T);
while (T--) {
scanf("%lld", &n);
if (n == 1) printf("1\n");
else {
printf("%lld\n", ((power(3, n - 1) - 1 + mod) % mod) * power(2, mod - 2) % mod * 3ll % mod + 1);
}
}
return 0;
}
```