[洛谷题解] CF837F Prefix Sums

发布于 2019-10-09  423 次阅读

题目链接：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的长度介于2和10之间，答案可能非常大，我们需要更好的做法。我们发现这题的情况有单调性，而且用k求x很难，而判断A^x中是否有元素大于等于k则看起来较为容易。（因此可以使用二分答案）

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

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

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

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

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

但是在这种情况下乘法运算仍然可能溢出，怎么办呢？__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

赏

undefined