前言

特别鸣谢：@Eucatastrophe‌ ，帮我把代码调好了。
其实不调的做法在考场能做，移到这里就炸了，数据问题吧
辉光借楼宣团https://www.acgo.cn/application/2042830309581336576

此题解不是正解！能过，但是并没有用到出题人想到的知识点（快速幂）

正文

思路

首先一个小结论（不会证，有证明过程那个题解没了）:

$$对于一个正整数n(n\geq2)，可以将其分解为：\\ n=p*2+q*3(p\geq0,q\geq0)\\ q越大，2^p+3^q越大。$$

人话：把一个≥2的数拆成$p$个$2$和$q$个$3$，那么$q$越大，这些数的乘积越大。
$q$最大时，$2^p+3^q$就是我们要求的最大乘积。
那么怎么找到最大的$q$呢？
反向思考，让$p$最小即可。
也就是：从小到大枚举$p$可能值，当$n-2*p$满足$q$的条件时，$n-2*p=3*q_{max}$。

实现

前置

输入：

ll n,ans = 1;cin >> n;

这里如果$n=1$会爆掉，所以加一个特判：

if(n==1){
    cout << 1 << endl;
    return;
}

然后是下面的实现（略）
最后是输出：

cout << ans << endl;

然后就是核心实现。

朴素实现

考虑简单的暴力，遍历p然后暴力求3^q：
首先遍历p：

while(n && n%3){
    n-=2;
    ans*=2;
}

这里不存储 $p$ , $q$ , 而是存储$n-2*p$。

如果这里除完了证明$q=0$，输出后返回即可。

if(!n){
    cout << ans << endl;
    return;
}

那么现在$3*q=n-2*p$。
然后在$ans$上乘$3^q$：

while(n){
    ans*=3;
    n-=3;
    ans%=MOD;
} 

预期分数$40pts$，实际过点$16/25$。（水了，考场这么做是$4/10$。这个数据很魔幻，低段多然后高段又很高）

瞎搞优化

正品是快速幂但是不会。

注意到$0\leq n\leq2$，所以上面循环-2的部分并不是大头。
但是如果加速$3^q$的部分正解需要快速幂，但是考虑到有的人不会快速幂。
但是根据初一上学期知识，$n^a=n^b+n^c(a=b+c)$。
所以，我们可以把$q$分解。
参考注释食用。

ll pw = pow(3,20),lst_pow=n/3;       //pow：拆分3^q的一个单位（20不会爆）  lst_pow：剩下的q。
pw%=MOD;                             //防止溢出
while(lst_pow>20){                   //还能拆
    __int128 tmp = ans;              //防溢出（__int128是C++的神秘128位整型）
    tmp*=pw;                         //这段都是乘上拆分单位然后取模
    tmp%=MOD;
    ans=tmp;                         //放回来
    lst_pow-=20;                     //更新lst_pow
}
__int128 ans2 = ans;                 //同上
for(int i=0;i<lst_pow;i++)
    ans2=(ans2*3)%MOD;               //出于神秘数据这里不能pow必须遍历，但是考场数据可以直接ans2*=pow(3,lst_pow)
ans2%=MOD;
ans=ans2;

预计$100pts$，实际过点$25/25$。

完整AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9;
void solve(){
    ll n,ans = 1;cin >> n;
    if(n==1){
        cout << 1 << endl;
        return;
    }
    while(n && n%3){
        n-=2;
        ans*=2;
    }
    if(!n){
        cout << ans << endl;
        return;
    }
    ll pw = pow(3,20),lst_pow=n/3;
    pw%=MOD;
    while(lst_pow>20){
        __int128 tmp = ans;
        tmp*=pw;
        tmp%=MOD;
        ans=tmp;
        lst_pow-=20;
    }
    __int128 ans2 = ans;
    for(int i=0;i<lst_pow;i++)ans2=(ans2*3)%MOD;
    ans2%=MOD;
    ans=ans2;
    cout << ans << endl;
}
signed main(){
    int t;cin >> t;while(t--)solve();
}

后记

你猜我上次Floyd那篇哪去了？答曰写太拉删了。
感谢@Xylophone指出我写的那就是一坨。
Upd 26-4-5:坏了证明那个题解没了。