#2033. 「GLR-R4」立夏

「GLR-R4」立夏

题目描述

  本题提供简要题意。

  天依给狐狸座准备的纱质发绳由白色和紫色的小格子组成,相同大小的小格子连成了一条足够长的带子。我们不妨把天依的手正捏着的位置标为第 00 格,向右依次是第 11 格、第 22 格,等等;向左依次是第 −1-1 格,第 −2-2 格,等等;天依将发绳对折起来,此时第 −1-1 格将于第 11 格重合,第 −2-2 格将于第 22 格重合……第 −k-k 格将与第 kk 格重合(kk 为正整数)。特别地,我们认为第 00 格保持原样,没有和其他格子重合,也没有和自己重合。

  由于发绳是半透光的,所以对折起来的发绳上的格子将可能出现三种颜色:白色、浅紫色和深紫色。两个白色的格子重合呈现白色,一个紫色和一个白色的格子重合呈现浅紫色,两个紫色的格子重合呈现深紫色。特别地,若第 00 格原来为白色,则折叠后也为白色,否则第 00 格原来为紫色,则折叠后为浅紫色。

  如果把白色记作 00,浅紫色记作 11,深紫色记作 22,以折叠后的第 00 格作为最低位,依次将每个格子颜色对应的数字记录下来,我们将得到一个长长的三进制数整数,记为 xx。现在,天依告诉你了 xx 的值,你能算出对折之前的发绳有多少种不同的样式吗?称两条发绳颜色不同,当且仅当存在一个整数 kk,使得两条发绳的第 kk 格上的颜色不相同。

  发绳款式丰富多样,你需要对 TT 个 xx 分别求出答案。

简要题意

  对于一个包含整数的集合 SS,定义其权值为 ∑a∈S3∣a∣\sum_{a\in S}3^{|a|}(即,枚举 SS 的元素 aa,计算 3∣a∣3^{|a|} 并求和)。给出非负整数 xx,计算有多少个集合的权值为 xx。注意集合不能包含重复元素。

输入格式

第一行一个整数 TT,表示你需要分别处理的数据组数。

接下来 TT 行,每行一个整数 xx,表示对折后发绳颜色所对应的三进制数。注意 xx 是以十进制输入的。

输出格式

输出 TT 行,第 ii 行一个整数,表示给出的第 ii 个 xx 对应的方案数。

样例

2
12
2
4
0

题目来源:洛谷 P9154