The main idea of the title
Given a length of
n
n
n sequence of non-negative integers
a
a
a, you need to perform a series of operations, and select an interval for each operation
[
l
,
r
]
[l,r]
[l,r], for all
l
≤
i
≤
r
l\leq i\leq r
l≤i≤r, will
a
i
a_i
ai? XOR on
w
w
w. You need to add all
a
i
a_i
ai? all become
0
0
0, find the minimum number of operations.
1
≤
n
≤
17
,
0
≤
a
i
≤
1
0
18
1\leq n\leq 17,0\leq a_i\leq 10^{18}
1≤n≤17,0≤ai?≤1018
Solution
First we set the sequence
d
d
d is sequence
a
a
The difference sequence of a (i.e.
d
i
=
a
i
⊕
a
i
?
1
d_i=a_i\oplus a_{i-1}
di?=ai?⊕ai?1?), so we can change the interval modification into a single-point modification (suffix interval modification) or a double-point modification (non-suffix interval modification).
After finding the difference sequence, we operate on the difference sequence. The meaning of the question becomes to convert all
d
i
d_i
di?becomes
0
0
0.
Let’s not consider it first
w
w
The value of w, and consider how to take the interval
[
l
,
r
]
[l,r]
[l,r]. Will
n
n
n numbers are regarded as
n
n
n points, the modification operation is regarded as an undirected edge (or self-loop) connecting two modification points. Then, a set of legal solutions consists of several connected blocks.
Considering the minimum number of edges of each connected block, let the size of this connected block be
x
x
x, then the lower bound of the minimum number of sides is
x
?
1
x-1
x?1 (i.e. a tree), the upper bound is
x
x
x (it is legal to connect one of the points to all other points, and then connect a self-loop to this point). We consider how to obtain the lower bound.
We find that this lower bound can be obtained if and only if the XOR sum of the numbers in the connected block is
0
0
0.
Necessity: Each operation is a double-point modification, then the XOR sum of the numbers in the entire connected block remains unchanged. If the final XOR sum is
0
0
0, then the XOR sum at the beginning must be
0
0
0.
Sufficiency: Consider using a chain to string together all the numbers in this connected block. Each time the chain head is deleted through XOR, and the next number becomes the new chain head after being affected. So, experience
x
?
1
x-1
After x?1 operations, the last number must be
0
0
0, no further operations are required.
In other words, we want to convert the difference sequence
d
d
d is divided into several subsequences, for each subsequence:
- When its XOR sum is
0
0
When 0, its weight is
x
?
1
x-1
x?1
- Otherwise, its weight is
x
x
x
We require a division method that minimizes the sum of weights.
It can be found that the answer is
n
n
The exclusive OR sum of the subsequence divided by n minus is
0
0
The number of subsequences is 0, then we need to make the XOR sum in the divided subsequences be
0
0
The number of subsequences of 0 is the largest, and you can use state pressure
D
P
DP
DP, let
f
s
f_s
fs? means
d
d
subsequence of d
s
s
How many XORs can s be divided into and the sum is
0
0
0 subsequence, then enumerate the subset of subsets to transfer.
You can first preprocess the XOR sum of each subsequence.
The time complexity is
O
(
3
n
)
O(3^n)
O(3n).
code
#include<bits/stdc + + .h>
using namespace std;
int n,f[1<<20];
long long a[25],d[25],v[1<<20];
int main()
{<!-- -->
// freopen("xor.in","r",stdin);
// freopen("xor.out","w",stdout);
scanf("%d", & amp;n);
for(int i=1;i<=n;i + + ){<!-- -->
scanf("%lld", & amp;a[i]);d[i]=a[i]^a[i-1];
}
for(int s=1;s<1<<n;s + + ){<!-- -->
for(int i=1;i<=n;i + + ){<!-- -->
if((s>>i-1) & amp;1) v[s]^=d[i];
}
}
for(int s=1;s<1<<n;s + + ){<!-- -->
for(int t=(s-1) & amp;s;t;t=(t-1) & amp;s){<!-- -->
f[s]=max(f[s],f[t] + f[s^t]);
}
if(v[s]==0) f[s]=max(f[s],1);
}
printf("%d",n-f[(1<<n)-1]);
return 0;
}