【JZOJ 杂题选讲】CF889E

题目大意

给出一个长度为n的序列a，我们定义
f(x,n)=x mod an
f(x,i)=x mod ai+f(x mod ai,i+1),1<=i<n
求最大的f(x,1)
n<=200000，1<=ai<=10^13

思路

令b[i]=x mod a[1] mod a[2] mod a[3]… mod a[i]
我们要最大化∑b[i]
有一个性质是一定有一个b[i]=a[i]-1，不然我把x+1所有的b[i]都会+1
然后显然我们有b[i]>=b[i+1]，我们的和也可以表示为ib[i]+k的形式
那么我们设F[i][j]表示b[i]=j时最大的k，注意到若x<j且F[i][x]<F[i][j]那么F[i][x]是没有用的，我们可以把[0,j]看做一个整体
考虑转移，若j<a[i+1]则直接转移到F[i+1][j]
否则[0,j]模a[i+1]会得到[0,a[i+1]-1],[0,j mod a[i+1]]两部分
考虑y为最大的满足y mod a[i+1]=a[i+1]-1
我们有F[i+1][j mod a[i+1]]=F[i][j]+i*(j-j mod a[i+1])
F[i+1][a[i+1]-1]=F[i][j]+i*(y-(a[i+1]-1))
容易发现这样做总共只有O(n)个状态，且每个状态只会转移O(log A)次，用map/set维护转移即可。
复杂度O(n log n log A)

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;

ll read() {
    char ch;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    ll x=ch-'0';
    for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x;
}

const int N=2*1e5+5;

struct node{
    ll j,k;
    node(ll _j=0,ll _k=0) {j=_j;k=_k;}
    friend bool operator < (node x,node y) {return x.j>y.j||x.j==y.j&&x.k>y.k;}
};

set<node> f;

typedef set<node> :: iterator it;
ll a[N];

int main() {
    int n=read();
    fo(i,1,n) a[i]=read();
    f.insert(node(a[1]-1,0));
    fo(i,1,n-1) {
        ll m=a[i+1],Mx=0;bool pty=0;
        while (1) {
            it pos=f.begin();
            ll j=(*pos).j,k=(*pos).k;
            if (j<m) break;
            pty=1;
            Mx=max(Mx,k+(ll)i*((j+1)/m*m-m));
            f.insert(node(j%m,k+(ll)i*(j-j%m)));
            f.erase(pos);
        }
        if (pty) f.insert(node(m-1,Mx));
    }
    ll ans=0;
    for(it pos=f.begin();pos!=f.end();pos++) {
        ll j=(*pos).j,k=(*pos).k;
        ans=max(ans,k+(ll)j*n);
    }
    printf("%lld\n",ans);
}