把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF 1635D Infinite Set
题目大意：给你一个a数组（大小范围为2e5），之后根据a创造一个不重复集合S，S中首先包含a中的所有数，其次包含S中所有数y的二倍加一(2y+1)和四倍(4y)，可以很容易看出S是一个无穷集合。
要求S中小于2^p的数字的个数。

解：

很容易就能看出这是一道数位，要问为什么，因为按二进制划分区间的话（[1],[2,3],[4,5,6,7]…这样）2Y+1得到的数显然是Y的后一区间，而4Y则在后二区间，所以显然可以得到：对于同一个起源的数，一个区间的数的数量等于前两个区间的数量和。那么我只要将a中的数全都塞进区间里然后做一次到p的斐波那契数列就完了……
不过问题在于如何去重，a中的两个数可能是同源的（比如2,5,8都可以通过2来得到）。既然都说“同源”了，那么找到“源”不就行了，可以很容易地发现，源其实都是最小的数，观察题目中的转化式子：如果一个数是转化过来的，如果它是奇数，则它只能由2y+1得到，如果是偶数，则它只能由4y得到，这样一来我就能轻松地算出它的“源”，顺便发现了一个没什么用的性质：所有数的源都是1或者2，这让你可以放心地把记录源的数组开的只有两个数字大小（虽然本来也只需要2e5）。
之后就是把源添加进去然后一路斐波那契加到p的位置，最后求个和就好了。
虽然全程没有提到位运算但显然是bitmask的一道题目，算是简单的思维题了，作为1800分的DIV2 D题真的好吗（可惜那场我没打。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#define _crt_secure_no_warnings
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <cstring>
#include <string>
#define ll long long
#define maxn 200005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
using namespace std;

ll dp[maxn];
map<ll, int> v;
ll a[maxn];
int pos(ll n) {
	int st = 1;
	ll tmp = n;
	while (tmp != 1) {
		st++;
		tmp = tmp / 2;
	}
	return st;
}


int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n, p;
	cin >> n >> p;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++) {
		ll tmp = a[i];
		int f = 0;
		while (tmp > 1) {
			if (tmp % 2 == 1) {
				tmp = tmp / 2;
			}
			else {
				if (tmp % 4 == 0) {
					tmp = tmp / 4;
				}
				else break;
			}
			if (v[tmp] == 1) {
				f = 1;
				break;
			}
		}
		if (f == 0) {
			v[a[i]] = 1;
			dp[pos(a[i])]++;
			//cout << "dp." << pos(a[i]) << "++" << endl;
		}
	}
	ll ans = dp[1];
	for (int i = 2; i <= p; i++) {
		dp[i] += dp[i - 1] + dp[i - 2];
		dp[i] = dp[i] % mdl;
		ans = (ans + dp[i]) % mdl;
	}
	cout << ans;
}