#D0192. 有趣的&运算

有趣的&运算

题目描述

&,中文读作“与”。与运算是位运算中非常重要的一种运算。规则和同学们熟知的if语句中的&&很像,一句话总结,有0则为0。

我们可以给出其四种运算规则:1&1=1,1&0=0,0&1=0,0&0=0。

如果我们想计算两个十进制数x和y进行与运算的结果,我们需要将两个十进制数先写为二进制数,然后上下对其进行按位计算。

举个例子,5&7的计算方法如下: 5=(101)25=(101)_27=(111)27=(111)_2

101111101101\\ \frac{111}{101}

(101)2(101)_2=510

所以5&7的结果就是5。

当然,编程中更加容易,你只需要写一行代码即可:

cout<<(5&7)<<endl;

现在TooY0ung给出 nn 个正整数,a1,a2...ana_1,a_2...a_n

定义g(l,r)=a[l]g(l,r)=a[l]&a[l+1]a[l+1]&......&a[r]a[r],你可以将这n个数划分为任意段连续的子段[1,r1],[r1+1,r2]...[rm1+1,n][1,r_1],[r_1+1,r_2]...[r_{m-1}+1,n]

g(1,r1)+g(r1+1,r2)+...+g(rm1+1,n){g(1,r_1)+g(r_1+1,r_2)+...+g(r_{m-1}+1,n)}的最小值。

输入格式

第一行一个整数 nn。 接下来一行 nn 个正整数。

输出格式

一行一个整数。

3
1 2 3
0

样例解释

分为[1,2],[3],结果为3。 分为[1],[2,3],结果为1。 分为[1,2,3],结果为0。

数据规模与约定

对于 100%100\% 的数据,0<n2000000 < n \le 2000001ai1091\le a_i \le 10^9

  • 子任务1(30分):n=2n=2
  • 子任务2(30分):n10n \le 10
  • 子任务3(40分):没有特殊限制。