Prefix Sums

在 n >= 4时候直接暴力。

n <= 4的时候二分加矩阵快速幂去check

#include<bits/stdc++.h>
#define LL long long
#define LD long double
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = 2e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-;
const double PI = acos(-); const int MN = ;
struct Matrix {
LL a[MN][MN];
Matrix() {
memset(a, , sizeof(a));
}
void init() {
for(int i = ; i < MN; i++)
a[i][i] = ;
}
Matrix operator * (const Matrix &B) const {
Matrix C;
for(int i = ; i < MN; i++)
for(int j = ; j < MN; j++)
for(int k = ; k < MN; k++) {
C.a[i][j] += 1.0 * a[i][k] * B.a[k][j] <= 2e18 ? a[i][k] * B.a[k][j] : INF;
C.a[i][j] = min(C.a[i][j], INF);
}
return C;
}
Matrix operator ^ (LL b) {
Matrix C; C.init();
Matrix A = (*this);
while(b) {
if(b & ) C = C * A;
A = A * A; b >>= ;
}
return C;
}
}; int n;
LL k;
LL a[N], b[N];
Matrix mat;
int Mat[][] = {
{, , },
{, , },
{, , }
}; int main() {
for(int i = ; i < ; i++)
for(int j = ; j < ; j++)
mat.a[i][j] = Mat[i][j];
scanf("%d%lld", &n, &k);
for(int i = ; i < n; i++) scanf("%d", &a[i]);
int m = n; n = ;
for(int i = , flag = ; i < m; i++) {
if(a[i]) flag = ;
if(flag) a[n++] = a[i];
}
LL mx = ;
for(int i = ; i < n; i++) mx = max(mx, a[i]);
if(mx >= k) {
puts("");
return ;
}
if(n >= ) {
for(int o = ; o <= && mx < k; o++) {
LL prefix = ;
for(int i = ; i < n && mx < k; i++) b[i] = i ? b[i - ] + a[i] : a[i];
for(int i = ; i < n && mx < k; i++) a[i] = b[i], mx = max(mx, a[i]);
if(mx >= k) {
printf("%d\n", o);
return ;
}
}
} else {
for(int i = n - ; i >= ; i--) a[ - (n - i)] = a[i];
for(int i = ; i < ( - n); i++) a[i] = ;
LL low = , high = (LL)1e18, ans = high;
while(low <= high) {
LL mid = (low + high) >> ;
Matrix tmp = mat ^ mid;
LL val = ;
for(int i = ; i < ; i++) {
val += 1.0 * a[i] * tmp.a[][i] <= 2e18 ? a[i] * tmp.a[][i] : INF;
val = min(val, INF);
}
if(val >= k) high = mid - , ans = mid;
else low = mid + ;
}
printf("%lld\n", ans);
}
return ;
} /*
*/

最新文章

  1. Menu与ActionBar的爱恨情仇
  2. jQuery 遍历 - each() 方法
  3. win2008server R2 x64 部署.net core到IIS上出现【Failed to load the dll from [C:\Program Files\dotnet\host\fxr\1.0.1\hostfxr.dll], HRESULT: 0x80070057】错误
  4. Windows和Unix下的编码问题
  5. MFC下无法为空间添加变量解决
  6. Window中调试HBase问题小结
  7. webstrom插件:如何设置才能让webstrom能提示bootstrap的语法
  8. apply和call的区别在哪里
  9. jQuery get/post区别及contentType取值
  10. ComboGrid( 数据表格下拉框)
  11. linux 软连接 硬连接
  12. go语言的for循环
  13. 报错:ch.qos.logback.core.joran.spi.JoranException
  14. mysql 远程连接 10038
  15. oracle杀掉连接
  16. Html fieldset、legend 标签
  17. (转)Awesome Human Pose Estimation
  18. android viewflipper的使用 实现图片滑动效果
  19. nginx配置http为1.0到1.1
  20. 数据库使用:sql server/mysql/sqlite

热门文章

  1. MS SqlServer还原数据库,出现媒体簇的结构不正确
  2. MVC5访问SQL Server数据库
  3. 安装snap及snap常安装软件
  4. layui 各种弹出框
  5. Linux学习之CentOS(三)--初识linux的文件系统以及用户组等概念
  6. centos7编译安装lnmp
  7. Bootstrap 固定底部导航栏菜单
  8. winform无需安装pdf阅读器打开pdf文件
  9. Nginx(./configure --help)
  10. 高性能JavaScript读后感