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$

因此时间复杂度为

算一下 $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;
}