题目链接:CF837F Prefix Sums
题意大意请见题目链接中的翻译。本题解将参照这个翻译进行讲解。
注意:题目中还有一个限制,即,“数列中必有至少两个元素是正数”。因此,答案不会是无穷大。
解题思路
本题解中,待求的值可能用表示。
我们发现,要解决这个问题,只需考虑某个数列中的最大值。因为如果最大值没有大于等于,其他值也不会大于等于。
对于一个数列(其中一定有正数),那么得到的开头一定有一个。这个可以直接忽略,因为它一定不是最大值。
于是我们可以改造函数,使得。
另外,初始数列的“前导0”无论如何进行前缀和,其值必然仍然是,并且不对后面的值产生影响。因此可以删去中的前导0。(此后的内容都在没有“前导0”的情况下考虑)
然后我们发现,如果此时的长度如果大于等于,那么只需进行很少的几次前缀和就会出现元素大于等于。因此,如果长度大于等于,可以直接暴力求解。
如果长度为,那么假设,则有。因此,待求的值可以通过除法得出:
如果的长度介于和之间,答案可能非常大,我们需要更好的做法。我们发现这题的情况有单调性,而且用求很难,而判断中是否有元素大于等于则看起来较为容易。(因此可以使用二分答案)
怎么个容易法呢?由于的长度很小,我们可以使用矩阵快速幂。设的长度为。定义一个的矩阵,其中对于所有,,其余情况。
则。
那么二分答案就可以实现了。
还有一个问题,矩阵快速幂溢出了怎么办?
由于我们只关心最后的数字是小于还是大于等于,因此类似于取模,我们计算时时时刻刻将结果和取。
但是在这种情况下乘法运算仍然可能溢出,怎么办呢?__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”,时间复杂度为,然后:
- 当时,仅仅进行一次除法,
- 当时,实测在极限数据下答案为。因此复杂度上限为。计算,因此不会有问题。
- 当时,二分答案占有复杂度(r是二分上界),而二分的
check
复杂度瓶颈在于矩阵乘法,复杂度上界为,另外“龟速乘法”的复杂度上界为,因此复杂度上限为。如果定二分范围为,计算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
Comments | NOTHING