二进制子集

时间：1s 空间：256M

题目描述：

给一个数 nnn，求所有的 xxx 满足在二进制下 xxx 的第 kkk 位如果是 111 ，则 nnn 的第 kkk 位必须为 111。求出的 xxx 按照升序输出。

比如 n=13n=13n=13，二进制为 110111011101，则总共有8个满足条件的 xxx ，他们的二进制为：

0,1000,1100,1001,1101,100,101,10,1000,1100,1001,1101,100,101,10,1000,1100,1001,1101,100,101,1，对应的数为：

0,8,12,9,13,4,5,10,8,12,9,13,4,5,10,8,12,9,13,4,5,1

输入格式：

第一行包含一个整数 nnn，保证 nnn 在二进制下为 111 的位数小于 151515。

输出格式：

升序输出所有 xxx。

样例输入：

13

样例输出：

0
1
4
5
8
9
12
13

约定与提示：

对于100%的数据，0≤n≤2600 \leq n \leq 2^{60}0≤n≤260， nnn 在二进制下为 111 的位数小于 151515。

本蒟蒻的代码:

#include <bits/stdc++.h>

typedef long ll;

using namespace std;

ll n;
int len;

vector<int> v;
set<ll> s;
void dfs(int u, ll res)
{
    if (u >= len)
    {
        s.insert(res);
        return;
    }
    dfs(u + 1, res);
    dfs(u + 1, res + (1ll * 1 << v[u]));
}

int main()
{
    cin >> n;
    long long t = n;
    int cnt = 0;
    while (t)
    {
        if (t & 1)
        {
            v.push_back(cnt);
            cnt++;
            t >>= 1;
        }
    }
    len = v.size();
    dfs(0, 0);
    for (auto it : s)
    {
        cout << it << endl;
    }
    return 0;
}