ABC466F

· · 题解

也许更好的阅读体验：个人博客。

分享一种比较小众的做法。

::::warning[闲话]{open} 第二次场切 F！！！而且这次瞪了 eps 秒就看出结论了。

观察题目可知，如果 A_i\le A_{i+1}，则 X\bmod A_i=(X\bmod A_i)\bmod A_{i+1}。所以我们可以把 A_{i-1}\le A_i 的 A_i 删去，使得数组 A 单调递减。下文中的数组 B 是已筛除后的数组 A。

发现这个式子没啥性质，尝试 dp。

设 F_i(x) 表示前 i-1 步执行完后得到的余数为 v，接下来依次模 B_i,B_{i+1},...,B_k，得到余数为 0，对于区间 [0,x] 之内的 v 数量。

我们最后需要求 F_1(N)-1。

如何去转移这个东西呢？以 F_i(x) 为例，如果 x\ge B_i，那么 x=q\times B_i+r 且 0\le r<B_i。

定 0\le t<q，区间 [tB_i,(t+1)B_i-1] 一定是模 B_i 后把余数全取了一遍的，所以单个区间的贡献是 F_{i+1}(B_i-1)。所有区间的贡献即 q\times F_{i+1}(B_i-1)。

对于剩下的区间 [tq,tq+r] 模 B_i 后一定是取完了 0 到 r 的余数，所以贡献是 F_{i+1}(r)。

如果 x<B_i 怎么办呢？直接扔给下一个模数即可，因为本身就是结果了。

综上，我们可以得到转移方程：

q\times F_{i+1}(B_i-1)+F_{i+1}(r)&x\ge B_i\\ F_{i+1}(x)&x<B_i \end{cases}

其中 q=\lfloor\frac{x}{B_i}\rfloor,r=x\bmod B_i。

边界处理：当我们 i=M+1 时（所有数都取模过了），只有为 0，才是合法的。

1&x=0\\ 0&x>0 \end{cases}

这个算法的时间复杂度是 O(NX)，无法通过。接下来这题最神的一个地方来了。

把转移方程看作一棵树，应当是这样子：

我们发现只有右边的 F_{i+1}(r) 是动态变化的，左边无论 q 是多少，都要乘 F_{i+1}(B_i-1)。我们设 C_i=F_{i+1}(B_i-1)，那么从 F_1(N) 往下走的 dp 方程就变成了递推。跟虚树是一个道理：不用的就滚蛋。

考虑倒着处理 C_i。每个 C_i 都跟求 F_1(N) 是一样的，在一条链上往下递推。如果模数大于 X，可以跳过。单个 C_i 的时间复杂度 O(\log M \log X)。

难点在如何证明时间复杂度是正确的。

::::success[处理单个 C_i 的代码]

int val=b[i]-1,pos=i+1,res=0;
if(val<mb){res=1;}
else{
    while(pos<=m){
        if(val<mb){res++;break;}
        int k;
        if(b[pos]<=val)k=pos;
        else{
            int l=pos,r=m,ans=m+1;
            while(l<=r){
                int mid=(l+r)>>1;
                if(b[mid]<=val){ans=mid;r=mid-1;}
                else l=mid+1;
            }
            k=ans;
            if(k==m+1)break;
        }
        int q=val/b[k];
        res+=q*v[k];
        val%=b[k];
        if(!val){res++;break;}
        pos=k+1;
    }
    if(val>0 && pos>m)res++;
}
v[i]=res;

::::

我们发现往下处理的时候，r=X\bmod (B_i-1)，至少变得比 X 的一半还小，所以外层循环的复杂度在 O(\log X) 级别。内层循环是一个二分，复杂度在 O(\log M) 级别。

对于 N 个 C_i 我们需要分别处理，预处理的总时间复杂度是 O(N\log N\log X)。

最后求 F_1(N) 一个道理。

都看到这里了，还不点赞。

那还是人吗？

::::success[正确代码]

//#pragma GCC optimize("O3")
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define is insert
#define fr(i,a,b) for(int i=(a);i<=(b);i++)
#define rf(i,a,b) for(int i=(a);i>=(b);i--)
#define prq priority_queue
#define gYES cout << "YES\n"
#define gNO cout << "NO\n"
#define gYes cout << "Yes\n"
#define gNo cout << "No\n"
const int MOD=1000000007;
const int Mod=998244353;
const int N=2e5+5;
using namespace std;
int max(int ax,int ay){return ax>ay?ax:ay;}
int min(int ax,int ay){return ax<ay?ax:ay;}
int abss(int ax){return max(ax,-ax);}
void fastIO(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
}
int a[N],b[N],v[N],n,x,m=1;
void solve(){
    cin>>n>>x;
    fr(i,1,n)cin>>a[i];            
    b[1]=a[1];            
    fr(i,2,n)if(a[i]<b[m])b[++m]=a[i]; 
    int mb=b[m]; v[m]=1;           
    rf(i,m-1,1){                      
        int val=b[i]-1,pos=i+1,res=0;
        if(val<mb){res=1;}
        else{
            while(pos<=m){            
                if(val<mb){res++;break;}
                int k;
                if(b[pos]<=val)k=pos;
                else{
                    int l=pos,r=m,ans=m+1;  
                    while(l<=r){
                        int mid=(l+r)>>1;
                        if(b[mid]<=val){ans=mid;r=mid-1;}
                        else l=mid+1;
                    }
                    k=ans;
                    if(k==m+1)break;        
                }
                int q=val/b[k];
                res+=q*v[k];
                val%=b[k];
                if(!val){res++;break;}
                pos=k+1;
            }
            if(val>0 && pos>m)res++;      
        }
        v[i]=res;
    }
    int c=x,ans=0;
    fr(i,1,m){                       
        if(c<b[i])continue;
        int q=c/b[i];
        ans+=q*v[i];
        c%=b[i];
    }
    cout<<ans;
    //以下为清空
    m=1;
    cout << "\n";
}
signed main(){
    fastIO();
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

::::