深夜写题解系列，话说这题暑假的时候就在LOJ上做掉了，然后今天看到Luogu上有就去交了一下，发现没写过题解，赶紧来补一下
说句题外话APIO2015的题目好水啊
首先考虑按位取或的过程，很显然要从二进制位从高到低贪心，尽量地让这一位能取\(0\)，那么就是考虑怎么判断这一位能否取到\(0\)的过程了
考虑直接设一个状态\(f_{i,j}\)表示把前\(i\)个数分成\(j\)段是否满足条件，最后看一下\(f_{n,i}(i\in [A,B])\)是否有\(1\)即可
那么转移也很简单，记录一下前缀和，然后向前枚举一个点转移，那么这段区间和在这一位上必须是\(0\)同时选择这一段不能使答案变大，这个详见代码的转移
因此我们现在有了一个\(O(n^3\log \sum Y_i)\)的做法，可以通过前4个Subtask
那么再看一下第5个Subtask有什么特殊之处，仔细一看会发现它的\(A=1\)！
那么很显然之前的DP之所以会慢就是因为考虑了答案的下界，但现在我们不用考虑了，直接考虑求出分开的最少段数，判断是否小于\(B\)即可，同样转移的方法和上面类似
所以这部分的复杂度是\(O(n^2\log \sum Y_i)\)的，两者综合即可通过此题
#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int R=40,N=2005;
int n,l,r,a[N]; long long ans;
namespace Case1 //n<=100 solver
{
const int MN=105;
bool f[MN][MN];
inline bool check(CI idx)
{
RI i,j,k; memset(f,0,sizeof(f));
for (f[0][0]=i=1;i<=n;++i) for (j=1;j<=i;++j)
{
long long sum=a[i]; for (k=i-1;~k;--k)
f[i][j]|=f[k][j-1]&&(!((sum>>idx)&1))&&((((sum>>idx)<<idx)|ans)==ans),sum+=a[k];
}
bool flag=0; for (i=l;i<=r;++i) flag|=f[n][i]; return flag;
}
};
namespace Case2 //l=1 solver
{
int f[N];
inline bool check(CI idx)
{
RI i,j; for (memset(f,127,sizeof(f)),f[0]=0,i=1;i<=n;++i)
{
long long sum=a[i]; for (j=i-1;~j;--j)
{
if ((!((sum>>idx)&1))&&((((sum>>idx)<<idx)|ans)==ans))
f[i]=min(f[i],f[j]+1); sum+=a[j];
}
}
return f[n]<=r;
}
};
int main()
{
RI i; for (scanf("%d%d%d",&n,&l,&r),i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=40;~i;--i) if (!(n<=100?Case1::check(i):Case2::check(i))) ans|=(1LL<<i);
return printf("%lld",ans),0;
}