| 题目名称 | 1819. [CF 388D]Fox的完美集合 |
|---|---|
| 输入输出 | foxandperfectsets.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 25 |
| 题目来源 |
 cstdio
于2014-11-19加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：1， 通过率：100% | ||||
 cstdio |
100 | 0.014 s | 0.32 MiB | C++ |
| 关于 Fox的完美集合 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
数位DP……
| ||||
1819. [CF 388D]Fox的完美集合
★★ 输入文件：foxandperfectsets.in
输出文件：foxandperfectsets.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
福克斯·雪儿（Fox Ciel）正在学习数学。
她称一个包含非负整数的非空集合S是完美的，当且仅当对于任意
(a可能等于b)，都有
。其中xor是异或的意思。
请计算完美集合的数量，要求集合只包含不超过k的整数。答案可能非常大，只需要输出它摸1000000007（即10^9+7）的值
【输入格式】
一行一个整数k（0<=k<=10^9）。
【输出格式】
一行一个整数，即符合条件的完美集合数量模10^9+7的值。
【样例】
以下为四组样例：
Input
1
Output
2
Input
2
Output
3
Input
3
Output
5
Input
4
Output
6
【提示】
在样例1中，有2个这样的集合：{0}和{0,1}。注意{1}不是完美集合，因为1 xor 1 = 0但{1}不包含0.
在样例4中，有6个这样的集合：{0},{0,1},{0,2},{0,3},{0,4},{0,1,2,3}。
【来源】
Codeforces Round #228 (Div.1)