CF837F Prefix Sums 题解

题意：

考虑函数 \(p(x)\)，其中 \(x\) 是含有 \(n\) 个元素的数组 \(x_1, \cdots, x_n\)，它返回一个新的含有 \(n+1\) 个元素的数组 \(y_0,y_1, \cdots, y_n\)，满足 \(y_k = \sum\limits_{i=1}^k x_i\)。

你有一个无限的数组序列 \(A^0, A^1, A^2, \cdots\)，其中 \(A^0\) 由输入给出，且对于每个 \(i \geq 1\)，都有 \(A^i = p \left( A^{i-1} \right)\)。你还有一个正整数 \(m\)，你需要找到最小的 \(i\)，使得 \(A^i\) 中存在 \(\ge m\) 的项。

输入格式：

第一行包含两个正整数 \(n, m~(2 \leq n \leq 2 \times 10^5,0\le m \leq 10^{18})\)，其中 \(n\) 表示数组 \(A_0\) 的大小。

第二行包含 \(n\) 个正整数 \(a_1, a_1, \cdots, a_n~(0\le a_i \leq 10^9)\)，表示原始的数组 \(A_0\)。

保证 \(A_0\) 中至少有两个正数。

输出格式：

输出一行一个整数，表示使得 \(A^i\) 中存在 \(\geq m\) 的项的最小 \(i\)。

注意到前导的 \(a_i = 0\) 是没有意义的

因为它不会改变后面前缀和的值，所以我们直接去掉即可。

注意到答案具有单调性，考虑二分最小的前缀和次数 \(k\) ，使得 \(A^k\) 存在大于等于 \(m\) 的项。

因为前缀和数组在 \(k\ge 1\) 时是单调不降的，所以我们只需要考察 \(A^k\) 的第 \(n\) 项是否大于等于 \(m\) 。

根据 k阶前缀和公式， \(k(k\ge 1)\) 阶前缀和的 \(n\) 项为 \[ \sum_{i=1}^n\dbinom{n+k-i-1}{k-1} a_i \] ~~根据经验来看~~，这个 \(k\) 阶前缀和在 \(n\) 一定时的增长速率是很快的。

考虑最简单的序列 \(1,0,0,\cdots\) ，则 \(A^k\) 的第 \(n\) 项为 \(\binom{n+k-2}{k-1}\) 。~~上 Python 打个表试试~~

n = int(input()); k = int(input()); 
fac = [0 for i in range(1,n+k+15)]; 
fac[0] = 1; 
for i in range(1,n+k+5): fac[i] = fac[i-1] * i; 
print("{0:e}".format(fac[n + k - 2] // fac[k-1] // fac[n-1]));

可以发现在 \(n=20,k=60\) 时的值已经到了 \(6.71\times 10^{17}\) 。

也就是说，当 \(n\ge 20\) 时，我们可以直接暴力去算这个 \(k\) 阶前缀和（所以这种情况不用二分）。

当 \(n < 20\) 时，由于 \(\binom{n+k-i-1}{k-1} = \binom{n+k-i-1}{n-i}\) ，而 \(n-i < n\) ，因此可以直接暴力算组合数。

如果在运算的过程中会过大溢出，直接记为 INF 即可，因为肯定超过 \(m\) 了。

事实上在乘法里就溢出了，所以要用个有趣的技巧

计算 \(a\times \frac{b}{c}\) 的时候，我们可以计算 \(\frac{a}{d}\times b\times \frac{d}{c}\) ，其中 \(d = \gcd(a,c)\) 。

又到了~~神奇的~~时间复杂度分析。

对于二分 \(k\) 的情况，显然复杂度为 \(\mathcal{O}(n^2 \log k)\)
对于暴力算前缀和的情况，因为 \(\binom{n+k-1}{n-1}\approx \frac{(n+k)^n}{n!} \ge m\)

因此时间复杂度为 \[ \mathcal{O}(nk) = \mathcal{O}\left(n\left(\sqrt[n]{n! \cdot m}\right)\right) = \mathcal{O}\left(n^2\left(\sqrt[n]{m}-1\right)\right) \] 算一下 \(n=2\times 10^5,m=10^{18}\) 的情况，发现大约 \(8.29 \times 10^6\) ，可以过。下面是计算的代码。
```
n = int(input()); m = int(input()); 
print( "{0:e}".format(n * n * (pow(m,1/n)-1)) ); 
```

故时间复杂度为 \(\mathcal{O}\left(n^2 \log k\,\downarrow\, n^2\left(\sqrt[n]{m}-1\right)\right)\) ，其中 \(\downarrow\) 表示取左右两式的较小值。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5+15))

int n,m,l,r,b[N];
int _a[N], *a=_a;
int gcd(int a,int b) { return b == 0 ? a : gcd(b, a%b); }
void add(int &x,int y) { (x += y) >= INF ? (x = INF) : 0; }
int solve()
{
    for(int i=1; ;i++)
    {
        for(int j=2; j<=n; j++) add(a[j], a[j-1]);
        if(a[n] >= m) return cout << i << '\n', 0;
    }
    return -1;
}
int C(int n,int m)
{
    if(m*2 > n) m = n-m; // int res=1; __int128 t;
    int res=1,d,t;
    for(int i=1; i<=m; i++)
    {
        // t = (__int128)res * (n-i+1) / i;
        // res = t > INF ? INF : t;
        d = gcd(res,i); res /= d; t = (n-i+1) * d / i;
        (res <= INF / t) ? (res *= t) : (res = INF);
    }
    return res;
}
bool test(int x)
{
    int c,res=0;
    for(int i=1; i<=n; i++)
    {
        if(!a[i]) continue;
        c = C(n-i+x-1, n-i);
        if(c <= b[i]) add(res, a[i] * c);
        else res = INF;
    }
    return res >= m;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        if(cin >> a[i], a[i] >= m) return cout << "0\n",0;
    for(; !a[1]; ++a,--n);
    if(n >= 20) return solve();
    for(int i=1; i<=n; i++) a[i] ? (b[i] = INF / a[i]) : 0;
    for(l=1,r=m; l<r; )
    {
        int mid = (l+r) >> 1;
        test(mid) ? r = mid : l = mid+1;
    }
    cout << l << '\n';
    return 0;
}