# 【AT3623】[ARC084D] XorShift（思维）([at3623] [arc084d] xorshift (thinking))-其他

## 【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}$$

### 代码：$$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
}