「GLR-R4」立夏 Sol

FjswYuzu · 2023-03-12 18:45:59 · 题解

大家好，我是只会出签到题的退役壬！这里写份题解。

因为集合里面每一个数的权值都是 3 的幂次，不难考虑三进制。将 x 写成三进制数之后考虑。

首先观察，如果 x={(\dots 2)}_3，因为 3^0 只能选一个，所以答案一定是 0。

再考虑其他位。如果 3^x 要选两个或者零个，方案数为 1；否则可以选 x 也可以选 -x，方案数为 2。每位互不影响（因为不会进位），所以可以直接乘法原理。

int main(){
    LL T=read();
    while(T-->0)
    {
        LL k=read();
        if(k%3==2)
        {
            puts("0");
            continue;
        }
        k/=3;
        LL ans=1;
        while(k)
        {
            if(k%3==1)  ans*=2;
            k/=3;
        }
        write(ans),puts("");
    }
    return 0;
}