And non

Topic link ：luogu P3220

The main idea of the topic

Give you an operation called and not , Is to add up two numbers and take the opposite .
Then I'll give you some K Bit binary number , Ask how much you can get through operation in L~R The number in .

Ideas

A very interesting question ！

You consider this operation ：$not(A\&B)$
Yourself and yourself ：$not(A\&A)=not(A)$, Non operational

After the operation, it's not about ：$not(not(A\&A))=A\&A$, And operation .
That or operation also has ：$not(not(A)\&not(B))$
That XOR also has ：（ Just one true and one false ）$(A\&not(B))or(not(A)\&B)$

Then these four operations are available. It seems that everything can be done , Then consider looking for exceptions .
You will find that if for all the numbers given , There is either between two people $1$ Or both. $0$, You can't come up with $10,01$ These , So this is equivalent to forming several connected blocks .

Then we can digital DP Did .

Then let's consider why this is not enough , That is why the rest of the situation can .
（ Let's treat these bindings as a ）
We consider having XOR , Let's use the idea similar to linear basis , Consider finding out that only one is $1$ The situation of .
In this way, you can or get all .

How do you get a position ？ Let's consider no matter where else , We just need a place $1$.
Then we can count all the numbers , This one is $1$ Yes, it works normally , If it's not, it's reversed and reused , In this way, all you get together , This one is $1$, And it seems that everything else will be $0$.
When you think about it carefully, you will find that it is indeed like this , Because if the other one is $1$, Who is this one $1$ Where it is $1$, yes $0$ It also if $0$, That's exactly the same , Can binding be regarded as one ？

So it proves .

Code

#include<cstdio>
#include<cstring>
#define ll long long

using namespace std;

const ll N = 1005;
ll n, K, lim[60];
bool sam[60][60], sp[60];
ll L, R, a[N];

ll clac(ll R, ll wei, bool ding) {
    
	if (wei < 0) return 1;
	if (!ding) {
    
		ll num = 0; for (ll i = 0; i <= wei; i++) if (sp[i]) num++;
		return (1ll << num);
	}
	
	if (lim[wei] == -1) {
    
		ll re = 0;
		for (ll i = 0; i <= ((R >> wei) & 1); i++) {
    
			ll tmp = 0;
			for (ll j = 0; j < wei; j++) if (sam[wei][j]) lim[j] = i;
			re += clac(R, wei - 1, i == ((R >> wei) & 1));
			for (ll j = 0; j < wei; j++) if (sam[wei][j]) lim[j] = -1;
		}
		return re;
	}
	else {
    
		if (lim[wei] == 1 && !((R >> wei) & 1)) return 0;
		return clac(R, wei - 1, lim[wei] == ((R >> wei) & 1));
	}
}

ll work(ll R) {
    
	memset(lim, -1, sizeof(lim));
	if (R < 0) return 0;
	return clac(R, K - 1, (R >> K) ? 0 : 1);
}

int main() {
    
	scanf("%lld %lld %lld %lld", &n, &K, &L, &R);
	for (ll i = 0; i < K; i++) for (ll j = 0; j < K; j++) sam[i][j] = 1;
	for (ll i = 1; i <= n; i++) {
    
		scanf("%lld", &a[i]);
		for (ll k = 0; k < K; k++)
			for (ll kk = 0; kk < k; kk++)
				if (((a[i] >> k) & 1) ^ ((a[i] >> kk) & 1)) sam[k][kk] = sam[kk][k] = 0;
	}
	for (ll i = 0; i < K; i++) {
    
		sp[i] = 1;
		for (ll j = i + 1; j < K; j++) if (sam[i][j]) {
    sp[i] = 0; break;}
	}
	
	printf("%lld", work(R) - work(L - 1));
	
	return 0;
}