| 题目名称 | 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$ 的整数。答案可能非常大，只需要输出它模 $10^9+7$ 的值
【输入格式】
一行一个整数 $k$（$0 \leq k \leq 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)