P9499题解

N_z_ · 2023-08-05 20:31:51 · 题解

思路

我们从前往后加入 (v_i,c_i)，维护一个 (v,c) 组。
对于一组新的 (v_i,c_i,x_{i-1})。
我们首先将组里从后往前每 x_{i-1} 个并成一个元素，v 为他们的和，c 为 1，即需要减少新的 v 的代价来造出一个当前的 i。
然后加入 (v_i,c_i)，当当前 v_i 大于组里的 v 时，我们使得组里的 v 直接变成当前的 v_i，即 c_i 增加组里的 c，然后将组里的 {v,c} 丢掉。

我们证明这个做法的正确性。
我们首先证明组内关于 v 是单调不增的。这是容易的，贪心合并 x 个保证了这一点。
其次我们证明这一构造是最优的。具体的，我们可以证明 v 从后往前是使用最小代价造出 k 个 i 的方案，同时用 i 造 k 不劣于先用 i 造 j 再造 k(i<j<k)。以及我们并不会将劣的方案选到答案中，从而这一做法是最优的。

具体实现中，我们将 v 组中 >v_{\max} 的直接丢弃，在 x=1 的时候不干活，因为这些并不能带来贡献，这保证了复杂度在 O(n\log n)。

代码

#define int __int128
constexpr int p=998244353;
main()
{
    signed t;
    cin>>t>>t;
    while(t--)
    {
        int n;
        cin>>n;
        vector<int>c(n),v(n),X(n-1);
        cin>>v>>c>>X;
        int ans=v[0]*c[0];
        vector<pair<int,int>>p;
        p.push_back({v[0],c[0]});
        for(int x=1;x<n;x++)
        {
            if(X[x-1]>1)
            {
                vector<pair<int,int>>p_;
                int lst=0,llst=0;
                while(!p.empty())
                {
                    auto [u,v]=p.back();
                    p.pop_back();
                    if(lst!=0)
                    {
                        int fk=min(v,X[x-1]-llst);
                        lst+=fk*u;
                        llst+=fk;
                        v-=fk;
                        if(lst>1e10)break; 
                        if(llst==X[x-1])p_.push_back({lst,1}),lst=llst=0;
                        else continue; 
                    }
                    if(u*X[x-1]<=1e10)p_.push_back({u*X[x-1],v/X[x-1]}),v%=X[x-1];
                    else break;
                    lst=u*v;llst=v;
                }
                swap(p,p_);
                reverse(p.begin(),p.end());
            }
            ans+=v[x]*c[x]%(::p);
            while(!p.empty()&&p.back().first<=v[x])
            ans+=p.back().second*(v[x]-p.back().first)%(::p),c[x]+=p.back().second,p.pop_back();
            p.push_back({v[x],c[x]});
        }
        cout<<ans%(::p)<<endl;
    }
}

注：这是这份代码的头。