令 \(m\) 表示分的组数，\(s_i\) 表示第 \(i\) 组的和。
看到位运算，首先考虑按位贪心，从高到低。
可以先假设结果的所有位都是 \(1\)，然后再从高位到低位尝试换成 \(0\)。
于是问题转化为给定 \(x\)，是否有 \(m \in [A,B]\) 的方案满足 \((\mathop{\text{bitor}}\limits_{i=1}^n s_i) \mathop{\text{bitor}} x = x\)。
容易发现只需要满足每一个 \(s_i\) 都满足 \(s_i \mathop{\text{bitor}} x = x\) 即可。
于是就变成了一个睿智 DP。
首先设 \(f_{i,j}\) 表示前 \(i\) 个数分 \(j\) 段的可能性。
再设 \(sum_i = \sum\limits_{j=1}^i Y_j\)。 有转移 \[f_{i,j} = \mathop{\large\lor}\limits_{k < i,(sum_i - sum_k)\mathop{\text{bitor}} x = x} f_{k,j-1}\] 然后若 \(\mathop{\large\lor}\limits_{i=A}^B f_{N,i}\) 为真，则 \(x\) 合法。
然鹅当 \(N \le 2000\) 时，\(O(n^3 \log Y_i)\) 就过不去了。
然鹅注意到此时 \(A = 1\)。
换个状态，\(g_i\) 表示前 \(i\) 个要满足上述条件，最少分几组。
其实也很简单……
\[g_i = \min\limits_{j<i,(sum_i - sum_j)\mathop{\text{bitor}}x=x} g_j + 1\] 于是判一下 \(g_N \le B\) 即可。
复杂度 \(O(n^2 \log Y_i)\)。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using namespace std;
const int N = 2e3;
const int LG = 60;
int n,l,r;
long long s[N + 5],ans = (1LL << LG) - 1;
int f[N + 5][N + 5],g[N + 5];
int check(int op,long long x)
{
if(!op)
{
memset(f,0,sizeof f),f[0][0] = 1;
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= i;++j)
for(register int k = 0;k < i;++k)
if((s[i] - s[k] | x) == x)
f[i][j] |= f[k][j - 1];
for(register int i = l;i <= r;++i)
if(f[n][i])
return 1;
return 0;
}
else
{
memset(g,0x3f,sizeof g),g[0] = 0;
for(register int i = 1;i <= n;++i)
for(register int j = 0;j < i;++j)
if((s[i] - s[j] | x) == x)
g[i] = min(g[i],g[j] + 1);
return g[n] <= r;
}
}
int main()
{
scanf("%d%d%d",&n,&l,&r);
for(register int i = 1;i <= n;++i)
scanf("%lld",s + i),s[i] += s[i - 1];
for(register int i = LG - 1;~i;--i)
ans &= ~(1LL << i),!check(l == 1,ans) && (ans |= 1LL << i);
printf("%lld\n",ans);
}