题解 SP2319 【BIGSEQ - Sequence】

· · 题解

2^{100}\le 10^{31}

所以我们可以使用 __int128 而并不需要使用高精。

然后题目要我们把这堆数分 m 段，要求每段的“和”的最大值最小。

这显然二分答案。

然后考虑怎么 check：假设现在二分到的答案是 lim ，对于一个从 i 开始的段，我们要尽可能的找一个最长的 len ，使得 i,i+1,\cdots i+len 这堆数在二进制意义下 1 的个数的和小于等于 lim，这显然又可以二分 len，那么现在问题就变成了怎么快速求出 i,i+1,i+2,\cdots ,j-1,j 这堆数在二进制意义下 1 的个数的和。

设 f_i 为 0,1,2,\cdots,2^i 这堆数在二进制意义下 1 的个数的和，有：

f_i=2\times f_{i-1}+2^{i-1}-1

这个比较显然对吧，原本 f_{i-1} 是 00XXXXX... 再加上一个 010000...，然后 f_i 是原本的 f_{i-1} 再加上 01XXXXX... 和 10XXXXX... ，那么这两部分其实就是 f_{i-1} 再加上在 01XXXXX... 里多出来的 2^{i-1}-1 个 1

算出了 f_i ，我们可以利用这个来算出任意一个 x 的 0,1,2,\cdots,x 这堆数在二进制意义下 1 的个数和。

int calc(int x)
{
    int sum=0,dlt=0;
    for(int i=k;i>=0;--i)
        if(pow2[i]&x)
            sum+=f[i]+dlt*pow2[i],++dlt;
    return sum;
}

也就是这个 calc 函数，这个其实需要找规律：

0 | 0 0 0 0
1 | 0 0 0 1
2 | 0 0 1 0
3 | 0 0 1 1
4 | 0 1 0 0
5 | 0 1 0 1
6 | 0 1 1 0
7 | 0 1 1 1
8 | 0 1 0 0

假设我们现在要求 calc(7) ，那么二进制分解下 7=4+2+1

那么首先先把 f_4 中的部分加上去：

1 | 0 0 0 1
2 | 0 0 1 0
3 | 0 0 1 1
4 | 0 1 0 0

然后下一个是 f_2，因为 f_4 已经计算过了，4+2=6 所以我们要去 [5,6] 中算

5 | 0 1 0 1
6 | 0 1 1 0

然后我们再把 f_2 对应的 [1,2] 看一看

1 | 0 0 0 1
2 | 0 0 1 0

发现在 2^2 的位置都多出了 1

然后再看一下剩下的 f_1，[7,7]，和 f_1 对应的区间 [1,1]

7 | 0 1 1 1
1 | 0 0 0 1

这部分不但多出了之前 f_2 里多出来的那个 2^2 ，还有 2^1 也多出来了

然后你多试几个数，就能找到上面代码的规律

然后 0,1,\cdots,i-1 能求出来，0,1,\cdots , j 能求出来，减一下 i,i+1,\cdots , j-1,j 也能求出来

注意二分边界不要搞错

\texttt{Code:} 
// This code wrote by chtholly_micromaker(MicroMaker)
#include <bits/stdc++.h>
#define reg register
#define int __int128
#define ln puts("")
using namespace std;
template <class t> inline void read(t &s){
    s=0;reg int f=1;reg char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))s=(s<<3)+(s<<1)+(c^48),c=getchar();s*=f;return;}
template<class t,class ...A> inline void read(t &x,A &...a){read(x);read(a...);return;}
template <class t> inline void write(t x){if(x<0)putchar('-'),x=-x;int buf[40],top=0;
    while(x)buf[++top]=x%10,x/=10;if(!top)buf[++top]=0;while(top)putchar(buf[top--]^'0');
    return;}
int a[120];
int pow2[120],f[120];
int k,m;
inline int calc(int X)
{
    reg int sum=0,dlt=0;
    for(int i=k;i>=0;--i)
        if(pow2[i]&X)
            sum+=f[i]+dlt*pow2[i],++dlt;
    return sum;
}
inline int solve(int l,int r)
{
    return calc(r)-calc(l-1);
}
inline bool check(int lim)
{
    reg int pos=0,cnt=0;
    while(pos<pow2[k]-1)
    {
        reg int l=pos,r=pow2[k]-1,mid,ans=pos;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(solve(pos+1,mid)<=lim)
                ans=mid,l=mid+1;
            else
                r=mid-1;
        }
        ++cnt;
        pos=ans;
        if(cnt>m)
            return false;
    }
    return true;
}
signed main(void)
{
    read(k,m);
    pow2[0]=1;
    for(int i=1;i<=k;++i)
        pow2[i]=pow2[i-1]*2;
    f[0]=1;
    for(int i=1;i<=k;++i)
        f[i]=pow2[i-1]+f[i-1]*2-1;
    reg int l=1,r=f[k],mid,ans=f[k];
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid))
            ans=mid,r=mid-1;
        else
            l=mid+1;
    }
    write(ans),ln;
    return 0;
}