LibreOJ 2886 「APIO2015」巴厘岛的雕塑

令 m 表示分的组数，si 表示第 i 组的和。
看到位运算，首先考虑按位贪心，从高到低。

可以先假设结果的所有位都是 1，然后再从高位到低位尝试换成 0。
于是问题转化为给定 x，是否有 m∈[A,B] 的方案满足 (nbitori=1si)bitorx=x。
容易发现只需要满足每一个 si 都满足 sibitorx=x 即可。
于是就变成了一个睿智 DP。

首先设 fi,j 表示前 i 个数分 j 段的可能性。
再设 sumi=i∑j=1Yj。 有转移 fi,j=∨k<i,(sumi−sumk)bitorx=xfk,j−1

然后若 B∨i=AfN,i 为真，则 x 合法。

然鹅当 N≤2000 时，O(n3logYi) 就过不去了。
然鹅注意到此时 A=1。
换个状态，gi 表示前 i 个要满足上述条件，最少分几组。
其实也很简单……
gi=minj<i,(sumi−sumj)bitorx=xgj+1

于是判一下 gN≤B 即可。
复杂度 O(n2logYi)。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
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);
}