题目描述
有一天，你实验室的老板给你布置的这样一个实验。
首先他拿出了两个长度为 n 的数列 a 和 b，其中每个 ai 以二进制表示一个集
合。例如数字 5 = (101)2 表示集合 f1; 3g。第 i 次实验会准备一个小盒子，里面装
着集合 ai 所有非空子集的纸条。老板要求你从中摸出一张纸条，如果满足你摸出的
纸条是 ai 的子集而不是 ai-bi，ai-bi+1，...，ai-1 任意一个的子集，那么你就要 ***；
反之，你就逃过一劫。
令你和老板都没有想到的是，你竟然每次都逃过一劫。在庆幸之余，为了知道
这件事发生的概率，你想要算出每次实验有多少纸条能使你 ***
输入格式
第一行一个数字 n。
接下来 n 行，每行两个整数，分别表示 ai 和 bi。
输出格式
n 行，每行一个数字，表示第 i 次实验能使你 *** 的纸条数。
样例输入 1
3
7 0
15 1
3 1
样例输出 1
7
8
0
数据范围
对于 30% 的数据，n; ai; bi ≤ 100
对于 70% 的数据，n; ai; bi ≤ 60000
对于 100% 的数据，n; ai; bi ≤ 10^5
保证所有的 ai 不重复，bi < i
分析：其实只要枚举子集的时候不要一个一个枚举，用O(3^n)的方法枚举子集就能过了，然后记录每个子集出现的位置，看看是不是小于i - bi就可以了.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n, pos[100010], ans; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { ans = 0; int a, b; scanf("%d%d", &a, &b); int temp = a; while (temp) { if (pos[temp] < i - b) ans++; pos[temp] = i; temp = (temp - 1) & a; } printf("%d ", ans); } return 0; }