题解

思路

知道尽量拆分为3的乘积即可。

举个例子：$6=3+3=2+2+2$，得第一种拆法所得结果>第二种拆法。

试着枚举$Mod\ 3$的情况：

• 0：直接为 $3^{n/3}$。
• 1：用10举例。$10=3+3+3+4=3+3+3+1$，得第一种拆法所得结果>第二种拆法。那么遇到这种情况就选择少拆一个3，多一个4，使结果更大，即 $3^{n/3-1}$。
• 2：同样举例子，少拆凑5的结果小于正常拆，为 $3^{n/3}·2$。

注意点：

• 使用快速幂否则超时。
• 特判n==1，不然会计算 $3^{-1}$，你好TLE。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll Mod=1e9;

ll t,n,res;

ll Fast_Pow(ll x,ll y){
	ll res=1,v=x;

	while(y){
		if(y&1) res=res*v%Mod;
		v=v*v%Mod;
		y>>=1;
	}

	return res;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(nullptr);

	cin>>t;

	while(t--){
		cin>>n;

		res=1;
		if(n%3==2) res=Fast_Pow(3,n/3)*2%Mod;
		else if(n%3==0) res=Fast_Pow(3,n/3); 
		else if(n==1) res=1;
		else res=Fast_Pow(3,n/3-1)*4%Mod;

		cout<<res<<'\n';
	}

	return 0;
}