1308:Essentially identical number

时间限制: 2 S | 内存限制: 65536 KB
Accept: 0 | Submit: 0
[提交] [状态] [讨论版]
描述

定义一个操作 f(a),其功能是将一个十进制正整数 a 转换成二进制后,把它所有连续的 0 和 1 都合并,形成一个新的二进制数。

例如:我们假设 a 的二进制是 1000011100111000,把它所有连续的 0 和 1 都合并后就变成了 101010。

定义两个数字 a 和 b 本质上相同当且仅当 f(a) = f(b)。

现在有 n 个数字,我们把其中本质相同的数字归为同一类,问最后可以归成多少个类。

输入

第一行是一个正整数 n 代表数字的数量。(1 <= n <= 1e5)

然后是 n 个正整数,这些数字的范围在 [1,9e18] 以内。

输出

这 n 个数字可以归成多少个类,然后换行。

样例输入

3

5 6 13

样例输出

2

HINT

5 的二进制表示为 101,所以 f(5) = 101

6 的二进制表示为 110,所以 f(6) = 10

13 的二进制表示为 1101,所以 f(13) = 101

显然,这三个数字可以归为两类。

来源
Hello winter vacation Round#4