CF837F

jucason_xu · 2023-02-20 19:15:32 · 题解

主题和生成函数相关，但是最后也附上了不用生成函数的做法。

和本题主流的矩阵快速幂无关。

首先，我们发现这道题目“序列会增长”的情况完全就是唬人的，因为我们把 x_i 输入之后，y_i 永远是 0，而前导 0 在计算的过程中没有任何的作用。所以可以直接原地做前缀和。

我们还发现，除了序列 A^0，其他的序列都是递增的（A^i_j-A^i_{j-1}=A^{i-1}_{j}\ge 0），所以 s\gt 0 时，序列 A^s 存在 A^s_i\ge k 等价于 A^s_n\ge k。

然后，我们考虑二分答案，每次检测进行 a 次运算之后的序列是否满足条件。

首先考虑的是生成函数和卷积，因为如果我们构造生成函数 f(x)=A^0_1x+A^0_2x^2+\cdots 以及 \mathrm{I}(x)=1+x+x^2+x^3+\cdots，那么求 a 次前缀和的结果就是 f(x)\times(\mathrm{I}(x))^a。直接看第 n 位即可。求 (\mathrm{I}(x))^a 可以使用卷积意义下的快速幂进行，复杂度 O(n\log n\log a)，看上去可以过，但别忘了，我们这是在二分答案的 check，所以总复杂度还要多一个 \log k，铁定过不了。（而且系数和 k 取 \min 也可能达到 10^{18} 级别，点值表示后其大小和 complex 误差不是 FFT 配 __int128 所能承受的）

我们先把序列所有的前导 0 去掉，找到序列第一个 1 的位置，考虑它对答案的贡献。我们发现，只要序列的长度达到一定长度，只有开头一个 1 的序列的第 n 项就会以指数级增长（即 a 次运算后，第 n 项的级别是 O(n^a)。虽然我们知道这可能有一个很小的常数，但是不要紧，当 n\ge 10 的时候，达到 10^{18} 的时间也不会超过 500。更何况 a 会随着 n 的增大而减小，所以我们可以直接暴力做。

对于 n<10，我们考虑别的方法。

常见的思路是 O(n^3\log^2 k) 的二分答案和矩阵快速幂。但是我们前面已经思考了生成函数做法，不如将其推到底。

首先，直接暴力做卷积是可以做的，但是这就显得很怨种。我们都已经推到 n<10 了，再用多项式总是有点杀鸡用牛刀的感觉（而且点值表示后虽然不会爆 __int128 了，误差还是有点可怕）。

我们考虑看看 f(x)\times(\mathrm{I}(x))^a 这个式子，发现 A^0_i 对答案 (f\times\mathrm{I}^a)(x) 的第 n 项的贡献是 \mathrm{I}^{a-1}(x) 的第 n-i 项系数。

考虑求出这个东西，G(x)=\mathrm{I}^{a-1}(x)=\dfrac{1}{(1-x)^{a-1}}，求第 y 项就是求 \dfrac{G^{(y)}(0)}{y!}。而 G^{(y)}(x)=\dfrac{(a-1)\cdots(a+y-2)}{(1-x)^{a-1+y}}，则 \dfrac{G^{(y)}(0)}{y!}=\dfrac{(a+y-2)!}{(1-0)^{a-1+y}(a-2)!y!}={a+y-2 \choose y}

然后我们的 y=n-i，所以需要的 (f\times\mathrm{I}^a)(x) 的第 n 项其实就是 \sum_{i\le n}{{a+n-i-2\choose n-i+1}A^0_i}。

接下来，我们发现 n-i+1 很小，我们如果记 p=n-i+1,q=a+n-i-2，这个组合数就是 \dfrac{p(p-1)(p-2)\cdots (p-q+1)}{q!}，而上下都不超过 n 项，下面的 q! 不超过 3628800，所以我们可以先暴力做出 q!，然后用一个 __int128 暴力维护上面的乘积。一旦这个积的大小超过了 q!\times k，就直接返回 k 退出。然后扫 1 到 n，计算出第 n 项的答案，中途大于 k 就直接返回 1。当然我们记住我们是在二分答案的，组合数的计算也是 O(n) 的，n\lt 10 的部分复杂度是 O(n^2\log k)。

一些闲话：不会生成函数怎么推最后的组合数式子？

我们可以只看第 i 项，考虑它对答案的贡献。实际上就是抹掉前 i-1 项，贡献次数就是对一个 1 和 n-i 个 0 做 a 次前缀和之后的第 n-i+1 项。

我们发现，如果我们把 1 1 1 1 1 1 1... 这样的无穷序列排下来，求 x 次前缀和之后的第 y 项的话，其实就是在表 S_{i,j}=S_{i-1,j}+S_{j-1,i} 中求第 x 行的第 j 列。

如果我们把这个表列出来：

1 | 1 1 1 1 1
2 | 1 2 3 4 5
3 | 1 3 6 10 15
4 | 1 4 10 20 35

如此列下来，你会发现，它就是旋转 45 度之后的杨辉三角！如果我们把左下到右上对角线看作一行的话，S_{i,j}=S_{i-1,j}+S_{j-1,i} 正好满足组合数的递推形式。

那么，我们进行坐标变换，容易发现第 x 行的第 y 列（从 1 开始）对应到杨辉三角坐标之后，处在第 x+y-2 行的第 y-1 列（从 0 开始）。而此处的系数就是 {x+y-2\choose y-1}，代入得到 {a+n-i-2\choose n-i+1}。也就使用非生成函数的办法推出了这个式子。

#define rp(i,n) for(ll i=1;i<=n;i++)
#define rep(i,a,b) for(ll i=a;i<=b;i++)
ll n,k,a[200005];
__int128 A[200005];
inline __int128 C(ll n,ll m){
    __int128 res=1,f=1;
    rp(i,m)f*=i;
    rep(i,n-m+1,n){
        res*=i;
        if(res>=f*k)return k;
    }
    return res/f;
}
inline void solve1(){
    ll mx=0;
    rp(i,n)A[i]=a[i];
    int cur=0;
    while(A[n]<k){
        rp(i,n)A[i]=A[i-1]+A[i];
        cur++;
    }
    cout<<cur<<endl;
}
inline bool check(ll f){
    __int128 ans=0;
    if(f>=k)return 1;
    rp(i,n){
        ll x=f,y=n-i+1;
        __int128 dd=C(x+y-2,y-1);
        if(a[i]&&dd>=k)return 1;
        ans+=a[i]*dd;
        if(ans>=k)return 1;
    }
    return ans>=k;
}
inline void solve2(){
    ll l=1,r=1e18,mid,ans=0;
    while(l<=r){
        mid=l+r>>1;
        if(check(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    rp(i,n)cin>>a[i];
    rp(i,n)if(a[i]>=k){
        cout<<0<<endl;
        return 0;
    }
    int be=1;
    while(!a[be])be++;be--;
    rp(i,n-be)a[i]=a[i+be];n-=be;
    if(n>10)solve1();
    else solve2();
    return 0;
}
//Crayan_r