【AT3623】[ARC084D] XorShift(思维)([at3623] [arc084d] xorshift (thinking))

题目链接

  • 给定一个初始大小为 \(n\) 的自然数集合 \(\{a_1,a_2,\cdots a_n\}\),不断进行两种操作:若 \(x\) 在集合中,则将 \(2x\) 加入集合;若 \(x,y\) 在集合中(允许 \(x=y\)),则将 \(x\operatorname{xor}y\) 加入集合。
  • 求无限操作下去集合中将会有多少个小于等于 \(m\) 的数。
  • \(n\le6\),\(0\le m,a_i\le 2^{4000}\)

所有数的公约数

众所周知,异或可以视作二进制下的不进位加法或不退位减法。

抛开不进位和不退位两个限定词,仅考虑可以进行加法或减法,那么只要求出所有数的公约数 \(d\),显然 \(d\) 的倍数都可以被表示出来。

现在只能进行左移和异或操作,只需要修改一下约数的定义即可。

考虑如何求两个数 \(x,y\) 的公约数。不妨设 \(x\) 的最高位大于等于 \(y\) 的最高位,只需对 \(y\) 进行左移操作使它的最高位与 \(x\) 相同,然后用 \(x\) 异或这个数得到 \(x’\),则与 \(x\) 相比 \(x’\) 的最高位必然降低,然后递归求 \(y,x’\) 的公约数即可。

方便起见将上述给 \(x\) 异或 \(y\) 左移后的数的过程称作 \(x\) 向 \(y\) 取模(\(x\operatorname{mod}y\)),在之后还会用到。

这整个过程可以利用 bitset 优化。

答案的求解

假设公约数 \(s\) 的最高位为 \(h_s\),\(m\) 的最高位为 \(h_m\)。

首先显而易见的一点,若一个数 \(x\) 是 \(s\) 的倍数,则当大于等于 \(h_s\) 的位确定后,小于 \(h_s\) 的位有唯一的填法。(设 \(x\) 保留大于等于 \(h_s\) 的位后的值为 \(x_0\),则小于 \(h_s\) 的位需要填入 \(x_0\operatorname{mod} s\),取模参考先前的定义)

那么考虑第 \(h_s\sim h_m\) 位的填法,可以从高到低枚举第 \(i\) 位假设从这位开始不卡上界。如果这位为 \(0\) 则只能卡上界;如果这位为 \(1\) 则可以填 \(0\),若填 \(0\) 后面的位可以任填,第 \(h_s\sim i-1\) 位共有 \(2^{i-h_s}\) 种填法,且它们对应的小于 \(h_s\) 的位都必然能取到。

还有一种情况就是第 \(h_s\sim h_m\) 位全部卡上界,此时我们求出保留这部分后模 \(d\) 的值与 \(m\) 小于 \(h_s\) 的位比较,以确定这种情况是否有贡献。

代码:\(O(\frac{nm^2}{\omega})\)

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Rg register
#define RI Rg int
#define Cn const
#define CI Cn int&
#define I inline
#define W while
#define N 20
#define M 40000
#define X 998244353
using namespace std;
int n;struct INT {int h;bitset<M+1> o;}m,a,s,r;
char st[M+5];I void read(INT& S) {scanf("%s",st+1),S.o.reset(),S.h=strlen(st+1);for(RI i=1;i<=S.h;++i) st[i]&1&&(S.o.set(S.h-i+1),0);}
I INT operator % (INT x,INT y) {W(x.h>=y.h) {x.o^=y.o<<x.h-y.h;W(x.h&&!x.o.test(x.h)) --x.h;}return x;}//取模
I INT gcd(INT x,INT y) {if(!y.h) return x;if(x.h<y.h) return gcd(y,x);return Calc(y,x%y);}//求公约数
int main()
{
	RI i,t=0;for(scanf("%d",&n),read(m),i=1;i<=n;++i) read(a),s=gcd(s,a);
	RI p=1;for(i=s.h;i<=m.h;++i) m.o.test(i)&&(t=(t+p)%X),p=(p<<1)%X;for(r=m,i=1;i^s.h;++i) r.o.reset(i);//枚举每一位假设不卡上界;全卡上界,只留下第hs~hm位
	RI fg=1;for(r=r%s,i=s.h-1;i;--i) if(m.o.test(i)^r.o.test(i)) {r.o.test(i)&&(fg=0);break;}return printf("%d\n",(t+fg)%X),0;//判断全卡上界时是否小于等于m
}
————————

Title Link

  • Given a set of natural numbers \ (\ {a_1, a_2, \ cdots a_n \} \) with an initial size of \ (n \), two operations are continuously carried out: if \ (x \) is in the set, add \ (2x \) to the set; If \ (x, y \) is in the set (allow \ (x = y \)), add \ (x \ operatorname {xor}y \) to the set.
  • Find how many numbers less than or equal to \ (m \) will be in the set under infinite operation.
  • \(n\le6\),\(0\le m,a_i\le 2^{4000}\)

Common divisor of all numbers

As we all know, XOR can be regarded as non carry addition or non abdication subtraction under binary.

Leaving aside the two qualifiers of non carry and non abdication, only considering that addition or subtraction can be carried out, it is only required to find the common divisor \ (D \) of all numbers. Obviously, the multiples of \ (D \) can be expressed.

Now you can only move left and XOR. You only need to modify the definition of divisor.

Consider how to find the common divisor of two numbers \ (x, y \). It is advisable to set the highest bit of \ (x \) to be greater than or equal to the highest bit of \ (Y \), just move \ (Y \) to the left so that its highest bit is the same as \ (x \), and then use the number of \ (x \) XOR to get \ (x ‘\), then the highest bit of \ (x’ \) must be lower than that of \ (x \), and then recursively find the common divisor of \ (y, X ‘\).

For convenience, the above process of shifting the number of \ (x \) XOR \ (Y \) to the left is called \ (x \) modulo to \ (Y \) (\ (x \ operatorname {mod}y \), which will be used later.

The whole process can be optimized by BitSet.

Solution of the answer

Suppose the highest bit of the common divisor \ (s \) is \ (h_s \), and the highest bit of \ (m \) is \ (h_m \).

First of all, it is obvious that if a number \ (x \) is a multiple of \ (s \), when the bits greater than or equal to \ (h_s \) are determined, the bits less than \ (h_s \) have a unique filling method. (let \ (x \) keep the value after the bits greater than or equal to \ (h_s \) be \ (x_0 \), then the bits less than \ (h_s \) need to be filled with \ (x_0 \ operatorname {mod} s \), and refer to the previous definition for modulus)

Then, considering the filling method of the \ (h_s \ SIM h_m \), the \ (I \) bit can be enumerated from high to low, assuming that there is no upper bound from here. If this is \ (0 \), only the upper bound of the card can be; If this is \ (1 \), you can fill in \ (0 \). If you can fill in any bit after \ (0 \), there are \ (2 ^ {i-h_s} \) filling methods in the \ (h_s \ SIM i-1 \) bit, and their corresponding bits less than \ (h_s \) can be obtained.

Another case is that all the upper bounds of the \ (h_s \ SIM h_m \) bit are on the card. At this time, we find the value of retaining this part of the post module \ (D \) and compare it with the bit whose \ (m \) is less than \ (h_s \) to determine whether this situation contributes.

Code: \ (O (\ frac {nm ^ 2} {\ Omega}) \)

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Rg register
#define RI Rg int
#define Cn const
#define CI Cn int&
#define I inline
#define W while
#define N 20
#define M 40000
#define X 998244353
using namespace std;
int n;struct INT {int h;bitset<M+1> o;}m,a,s,r;
char st[M+5];I void read(INT& S) {scanf("%s",st+1),S.o.reset(),S.h=strlen(st+1);for(RI i=1;i<=S.h;++i) st[i]&1&&(S.o.set(S.h-i+1),0);}
I INT operator % (INT x,INT y) {W(x.h>=y.h) {x.o^=y.o<<x.h-y.h;W(x.h&&!x.o.test(x.h)) --x.h;}return x;}//取模
I INT gcd(INT x,INT y) {if(!y.h) return x;if(x.h<y.h) return gcd(y,x);return Calc(y,x%y);}//求公约数
int main()
{
	RI i,t=0;for(scanf("%d",&n),read(m),i=1;i<=n;++i) read(a),s=gcd(s,a);
	RI p=1;for(i=s.h;i<=m.h;++i) m.o.test(i)&&(t=(t+p)%X),p=(p<<1)%X;for(r=m,i=1;i^s.h;++i) r.o.reset(i);//枚举每一位假设不卡上界;全卡上界,只留下第hs~hm位
	RI fg=1;for(r=r%s,i=s.h-1;i;--i) if(m.o.test(i)^r.o.test(i)) {r.o.test(i)&&(fg=0);break;}return printf("%d\n",(t+fg)%X),0;//判断全卡上界时是否小于等于m
}