302044: CF388D. Fox and Perfect Sets
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Fox and Perfect Sets
题意翻译
福克斯·夏尔正在学习数论。 她认为一个非负非空集合$S$是完美的,当且仅当其中任意元素$a,b\in S$($a$可以等于$b$),且$a\bigoplus b\in S $。其中,$\bigoplus $代表异或运算,详见https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677?fr=aladdin 。 请计算以小于等于$k$的非负整数构成的完美集合的个数。这个答案可能会很大,所以请对$1000000007\ (10^9+7)$取模。 ## 输入输出格式 ### 输入格式: 第一行包含一个整数$k\ (0<=k<=10^9)$。 ### 输出格式: 输出一个整数,表示完美集合的个数对$1000000007\ (10^9+7)$取模后的值。 ## 说明 在样例1中,这里有两个满足条件的集合:$\{0\}$和$\{0,1\}$。其中,集合$\{1\}$并不是完美集合,这是因为$1\bigoplus1=0$,但是集合$\{1\}$中并不包含元素$0$。 在样例4中,有6个满足条件的集合:$\{0\},\{0,1\},\{0,2\},\{0,3\},\{0,4\},\{0,1,2,3\}$。 翻译提供者:David_Lei题目描述
Fox Ciel studies number theory. She thinks a non-empty set $ S $ contains non-negative integers is perfect if and only if for any ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF388D/c903e14df0afa987e9cf41a6200a241f6b8b2cd2.png) ( $ a $ can be equal to $ b $ ), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF388D/7498aa246f7bcda4dd31870c3686217d9c6cbaf1.png). Where operation $ xor $ means exclusive or operation (http://en.wikipedia.org/wiki/Exclusive\_or). Please calculate the number of perfect sets consisting of integers not greater than $ k $ . The answer can be very large, so print it modulo $ 1000000007 $ $ (10^{9}+7) $ .输入输出格式
输入格式
The first line contains an integer $ k $ ( $ 0<=k<=10^{9} $ ).
输出格式
Print a single integer — the number of required sets modulo $ 1000000007 $ $ (10^{9}+7) $ .
输入输出样例
输入样例 #1
1
输出样例 #1
2
输入样例 #2
2
输出样例 #2
3
输入样例 #3
3
输出样例 #3
5
输入样例 #4
4
输出样例 #4
6