[洛谷题解] CF837F Prefix Sums

题目链接:CF837F Prefix Sums


题意大意请见题目链接中的翻译。本题解将参照这个翻译进行讲解。

注意:题目中还有一个限制,即,“数列中必有至少两个元素是正数”。因此,答案不会是无穷大。


解题思路

本题解中,待求的值可能用x表示。

我们发现,要解决这个问题,只需考虑某个数列A^x中的最大值。因为如果最大值没有大于等于k,其他值也不会大于等于k

对于一个数列A(其中一定有正数),那么得到的p(A)开头一定有一个0。这个0可以直接忽略,因为它一定不是最大值。

于是我们可以改造函数p,使得p([1,1,1]) = [1,2,3]

另外,初始数列A^0的“前导0”无论如何进行前缀和,其值必然仍然是0,并且不对后面的值产生影响。因此可以删去A^0中的前导0。(此后的内容都在没有“前导0”的情况下考虑)

然后我们发现,如果此时A^0的长度如果大于等于10,那么只需进行很少的几次前缀和就会出现元素大于等于k。因此,如果A^0长度大于等于10,可以直接暴力求解。

如果A^0长度为2,那么假设A^0 = [a,b],则有A^x = [a,a\cdot x + b]。因此,待求的值可以通过除法得出:x_{min} = \lceil \frac{k-b}{a} \rceil

如果A^0的长度介于210之间,答案可能非常大,我们需要更好的做法。我们发现这题的情况有单调性,而且用kx很难,而判断A^x中是否有元素大于等于k则看起来较为容易。(因此可以使用二分答案)

怎么个容易法呢?由于A^0的长度很小,我们可以使用矩阵快速幂。设A^0的长度为n。定义一个n \times n的矩阵M,其中对于所有j \leq iM_{i,j} = 1,其余情况M_{i,j} = 0

A^x = M^x \cdot A^0

那么二分答案就可以实现了。

还有一个问题,矩阵快速幂溢出了怎么办?

由于我们只关心最后的数字是小于k还是大于等于k,因此类似于取模,我们计算时时时刻刻将结果和kmin

但是在这种情况下乘法运算仍然可能溢出,怎么办呢?__int128_t 我们可以使用类似于快速幂的方式,实现一种“龟速乘法”(即,使用加法实现乘法)。具体如下:

// 代码中limit代表k的值
int mxqmul(int a,int b) {
    if(b==0) return 0;
    int r = mxqmul(a,b>>1);
    r = min(r + r, limit);
    if(b&1) return min(r + a, limit);
    return r;
}

复杂度分析

删除“前导0”,时间复杂度为O(n),然后:

  • |A^0|=2时,仅仅进行一次除法,O(1)
  • |A^0|\geq 10时,实测在极限数据下答案为411。因此复杂度上限为O(411n)。计算411 \cdot 200000 = 82,200,000,因此不会有问题。
  • 2 \lt |A^0| \lt 10时,二分答案占有复杂度log(r)(r是二分上界),而二分的check复杂度瓶颈在于矩阵乘法,复杂度上界为n^2 \cdot log(r),另外“龟速乘法”的复杂度上界为log(long\ long) = 31,因此复杂度上限为O(log^2(r)\cdot n^2 \cdot 31)。如果定二分范围为[0,64356879284],计算Math.log2(64356879284)**2 * 10**2 * 31 == 3996507.528120665,因此也不会有问题。

代码

// status: [Accepted]
// oj:     [luogu]

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll

const int MAXN = 200001;
int arr[MAXN];
// 题目中的k。因为k一般用作循环变量,所以不作为变量名
int limit;
// A0的长度
int n;

// “龟速乘法”
int mxqmul(int a,int b) {
    if(b==0) return 0;
    int r = mxqmul(a,b>>1);
    r = min(r + r, limit);
    if(b&1) return min(r + a, limit);
    return r;
}

// 矩阵乘法封装类
struct Matrix:vector<vector<int> > {

    Matrix __construct(int l = 0, int w = 0, int v = 0)
    {
        assign(l, vector<int>(w, v));
        return *this;
    }

    Matrix(int l = 0, int w = 0, int v = 0)
    {
        assign(l, vector<int>(w, v));
    }

    unsigned sizeL() const {
        return size();
    }

    unsigned sizeW() const {
        return empty()?0:(*this)[0].size();
    }

    Matrix operator* (const Matrix &other) const {
        if(sizeW()!=other.sizeL()) {
            return Matrix(0,0,0);
        }

        int l=sizeL(),w=other.sizeW(),p=sizeW();
        Matrix ret(l,w,0);

        for(int i=0;i<l;i++) {
            for(int j=0;j<w;j++) {
                for(int k=0;k<p;k++) {
                    ret[i][j]+=mxqmul((*this)[i][k],other[k][j]);
                    ret[i][j] = min(ret[i][j],limit);
                }
            }
        }
        return ret;
    }
    Matrix operator*= (const Matrix &other) {
        *this=(*this)*other;
        return *this;
    }

    Matrix pow(int t) {
        if(t==0) {
            Matrix ret(sizeL(),sizeL(),0);
            for(int i=0;i<sizeL();i++) {
                ret[i][i]=1;
            }
            return ret;
        }
        if(t==1) {
            return *this;
        }
        if(t==2) {
            return (*this)*(*this);
        }
        Matrix tmp=pow(t/2);
        if(t%2==0) return tmp*tmp;
        else return (*this)*tmp*tmp;
    }

    Matrix pow_(int t) {
        *this=pow(t);
        return *this;
    }

    void oi_input() {
        for(int i=0;i<sizeL();i++) {
            for(int j=0;j<sizeW();j++) {
                scanf("%lld",&(*this)[i][j]);
            }
        }
    }

    void oi_output() {
        for(int i=0;i<sizeL();i++) {
            for(int j=0;j<sizeW();j++) {
                printf("%lld ",(*this)[i][j]);
            }
            printf("\n");
        }
    }
};

// 二分的check。如果Ap中存在大于等于limit的元素返回true,否则返回false
bool check(int p) {
    Matrix mt(n,n,0);

    for(int i=0;i<n;i++) {
        for(int j=0;j<=i;j++) {
            mt[i][j] = 1;
        }
    }

    Matrix ar(n,1,0);
    for(int i=0;i<n;i++) {
        ar[i][0] = arr[i+1];
    }

    ar = mt.pow(p) * ar;

    for(int i=0;i<n;i++) {
        if(ar[i][0] >= limit) return true;
    }
    return false;
}

// 删除前导0,返回删除后数列的长度
int unuqie(int *arr,int len) {
    int ptr = 0;
    for(int i=1;i<=len;i++) {
        if(arr[i] != 0 || ptr) {
            arr[++ptr] = arr[i];
        } 
    }
    return ptr;
}

// 功能相当于 (int)ceil((double)a/b)
// 用于A0的长度等于2的情况下。由于double的精度问题,并不能使用强转double并ceil的方法。
int ceilDiv(int a,int b) {
    return a/b + bool(a%b);
}

signed main() {
    scanf("%lld",&n);
    scanf("%lld",&limit);
    for(int i=1;i<=n;i++) {
        scanf("%lld",&arr[i]);
    }

    // 去除前导0
    n = unuqie(arr,n);

    // 判断 |A0| == 2
    if(n == 2) {
        printf("%lld\n",max(0ll, ceilDiv((limit - arr[2]), arr[1])));
        exit(0);
    }

    // 判断答案为0的情况(防止出现问题)
    for(int i=1;i<=n;i++) {
        if(arr[i] >= limit) {
            printf("0\n");
            exit(0);
        }
    }

    // 如果 |A0| >= 10,可以暴力迭代完成。
    if(n >= 10) {
        int cnt = 0;
        while(1) {
            cnt++;
            for(int i=1;i<=n;i++) {
                arr[i] += arr[i-1];
                if(arr[i] >= limit) {
                    printf("%lld\n",cnt);
                    exit(0);
                }
            }
        }
    }

    // 否则二分答案
    // 考虑二分边界的方法:
    //   如果check(mid)为true,那么mid值偏大或正好
    //     由于check(mid)为true,最终答案可能是mid,所以 r = mid (如果最终答案不可能是mid,取 r = mid - 1)
    //   如果check(mid)为false,那么mid值偏小
    //     最终答案不可能取mid,所以 l = mid + 1 (如果最终答案可能是mid,取 l = mid)
    // 随后考虑最容易死循环的情况,即 r - l == 1,来确定mid的取值
    //   如果令 mid = l+r - (l+r)/2,则此情况下mid = r:
    //     若check(mid) == true,那么执行 r = mid,即 r = r,此时二分范围没有变小,会造成死循环,所以应当令 mid = (l+r)/2
    int l = 0, r = 64356879284;
    while(l<r) {
        int mid = (l+r)/2;
        if(check(mid)) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    printf("%lld\n",l);
}


评测记录:R24947635

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注