50 pts
只需要按照题目意思模拟即可，得出以下打表程序。
#include<iostream>
#include<cstring>
#include<cmath>
int t,n;
int mc(std::string x,std::string y){
int res=0;
for(int i=0;i<x.size();i++){
if(x[i]==y[i])res++;
}
return res;
}
int v3(int x){
int res=0;
for(int i=2;i<=x;i++)
while(x%i==0){
if(i==3)res++;
x/=i;
}
return res;
}
int main(){
std::cin>>t;
while(t--){
std::cin>>n;
std::string a,b,c;
for(int i=1;i<=pow(3,n);i++){
if(i%2==1)a+="1";
if(i%2==0)a+="0";
if(v3(i)%2)c+="1";
if(v3(i)%2==0) c+="0";
if(i%2==1)b+="0";
if(i%2==0)b+="1";
}
int rtl=std::min(mc(a,c),mc(b,c));
std::cout<<rtl<<'\n';
}
}
请注意，这个程序会超时的，所以我们需要把 \(n \leqslant 10\) 的答案套出来，然后输出。
100 pts
还记得上面的打表程序吗，用它套出来 \(n \leqslant 10\) 的结果是 1,4,13,40,121,364,1093,3280,9841,29524。拿这个数列的第 \(6\) 项举例，$364 = 3^0 + 3^1 + 3^2 + 3^3 +3^4 + 3^5 $，稍微分析一下就可以知道求这个数列的公式是 \(\frac{3^n-1}{2}\)。注意 \(n \leqslant 10^{18}\)，要使用快速幂。
#include<iostream>
const int mod=1e9+7;
#define ll long long
ll qpow(ll a,ll b){ll res=1;while(b>0){if(b%2==1)res=(res*a)%mod;a=(a*a)%mod,b/=2;}return res;}
int main(){
int t;
std::cin>>t;
while(t--){
ll n,res=0;
std::cin>>n;
res=(qpow(3,n)-1+mod)%mod;//实际上就是(3^n-1)对1e9+7取模，确保结果非负。
res=(res*qpow(2,mod-2))%mod;//就是将(3^n-1)对1e9+7 取模的结果乘以2的逆元并再次对1e9+7取模
std::cout<<res<<'\n';
}
}