P10861 [HBCPC2024] MACARON Likes Happy Endings

MACARON is going to read a book, which contains $n$ chapters, and the $i$-th chapter has $a_i$ characters. MACARON wants to read this book in the next $k$ days. On each day, he either reads several chapters from the first unread chapter, or just takes a rest (does not read the book), but he should finish his reading in $k$ days. MACARON enjoys his reading time and likes happy endings, so he does not want to be too sad during these days. He has an unlucky number $d$, because he thinks number $d$ will lead to a bad ending. We use a sadness value to quantify his mood on each day. On the $i$-th day, if he reads, suppose that he reads chapters from $L_i$ to $R_i$. The sadness value of this day is the number of intervals $[l, r]$ such that $L_i\leq l\leq r\leq R_i$ and $\bigoplus_{i=l}^r a_i=d$. The $\oplus$ denotes the bitwise XOR operator. If he doesn't read, let the sadness value be $0$. MACARON wants to arrange his reading schedule to minimize the sum of sadness value in $k$ days. Can you help him find the minimum value?

The first line contains three integers $n, k$ and $d$ ($1\leq n\leq 10^5, 1\leq k\leq \min(n, 20), 0\leq d\leq 10^6$) --- the number of chapters, the days for reading, and the unlucky number. The second line contains $n$ integers $a_i$ ($0\leq a_i\leq 10^6$) --- the number of characters in each chapter.

Output a single integer denoting the minimized sum of the sadness value.

Here is an optimal schedule for reading: - on the first day, just take a rest, and the sadness value is 0; - on the second day, read from chapter 1 to chapter 3, and the sadness value is 0; - on the third day, read from chapter 4 to chapter 7, and the sadness value is 2; - on the fourth day, read from chapter 8 to chapter 10, and the sadness value is 1.