CF-Round #631-div2-D题&div1B题

CF-Round #631-div2-D题&div1B题

D. Dreamoon Likes Sequences

传送门

每次只要写异或的（什么位运算啊这种题）我就吃老大的亏emmm.我是真的对这些位运算很迷啊。。（看看我电路课都是怎么活过来的。。）

这道题是构造题。
让你构造一个序列a满足以下要求：
1.序列a的长度为n，n >= 1;
2.给定的界限d;
满足1 <= a1 < a2 < a3 < a4 < … < d;
3.构造出另外的一个序列b[]；
b[1] = a[1];
当i大于1的时候：
b[i] = b[i - 1] ^ a[i];
要求b1 < b2 < b3 < b4 < b5… < bn;

解题思路：
我们可以枚举一下异或的要求：
要使得严格大于的话，并且是异或之后

为什么？因为观察一下每个数的最高位1，只有后面一个数的最高位的1的位置比当前的最高位的1的位置高。才可能满足异或之后严格大于的要求。
要不然最高位的1位置相同，那么异或之后为0.下一个数小于当前数。不满足严格大于要求。

所以我们用h(x)代表数x的二进制下的最高位1的位置。从0开始计数
比如：
h(1) = 0；h(2) = h(3) = 1;
h(4) = h(5) = h(6) = h(7) = 2;…
我们可以直接观察到要满足题目要求的序列：h(a[i]) = h(b[i]);因为b[i]是要求严格递增的。但是b[i] = b[i - 1] ^ a[i]运算之后的结果。毫无疑问h(a[i]) > h(b[i - 1])。因为这样才能保证递增嘛。所以h(b[i]) = max(h(a[i]）, h(b[i - 1])） = h(a[i]);
成立。
我们进而可以得到：h(a[i]) > h(a[i - 1]);
这个式子就代表着我们上面图片的要求：
0~1范围最多能选1个；
2~3范围最多能选1个；
4~7范围最多能选1个…等等

但是考虑到边界的范围d:
所以我们的当前可以选择的个数；
当h(a[i]) = v时：
我们可以选择的区间是：[2 ^ v, min(d, 2^(v + 1) - 1)];
因为我们构造的序列长度只需要>=1嘛。所以当前区间可以选也可以不选。
所以我们当前选择的情况有上面的区间中数的个数+不选的情况：
min(d, 2^(v + 1) - 1) - 2 ^ v + 2;
最后我们只需要累乘一下就可以啦~

代码部分判断的情况：如果2^i次方已经大于d了的话。就可以break了。
最后ans–的情况是代表：有一种情况是全部都不选。长度为0的时候。这种情况不满足要求。需要减掉。
另外ans可能在–之后小于0；
因为我们进行的求余的操作可能恰好碰到整除的情况最后ans = 0;比如mod = 1时。
然后再–就会变成负数。
所以我们特判一下如果小于0，再加上m即可。

我在求模那个wa了好多次。。
我在还没有累乘的时候先mod了，然后再乘（这样子的mod没有效果。这样子可能直接会越界）
应该先乘后mod: )

代码部分：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int t;
int d, m;
ll ans;

int main()
{
	cin >> t;
	while (t--)
	{
		cin >> d >> m;
		ans = 1;
		for (int i = 0; i < 30; i++)
		{
			if (d < (1 << i))
			{
				break;
			}
			ans = ans * (min(d, (1 << (i + 1)) - 1) - (1 << i) + 2) % m;
		}
		ans--;
		if (ans < 0)
		{
			ans += 1ll * m;
		}
		cout << ans << endl;
	}
	return 0;
}