自动搬运

查看原文

来自洛谷，原作者为

	FjswYuzu Rainybunny狂热粉丝!111111 | Last Goodbye

搬运于2025-08-24 22:45:52，当前版本为作者最后更新于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;
}