[agc003e]Sequential operations on Sequence

前言

利用了经典性质的题。

题目大意

有一个数字串S，初始长度为n，是1 2 3 4 …… n。

有m次操作，每次操作给你一个正整数a[i]，你先把S无穷重复，然后把前a[i]截取出来成为新的S。

求m次操作后，每个数字在S中出现的次数。

做法

考虑这样一个过程，solve(x,l)表示在第x次操作后的S的前l位，我们希望获取每个数在这里面的出现次数（这个函数返回一个数组）。

不妨设S[i]表示第i次操作后的S每个数字出现的次数（即值是一个数组）

显然solve(x,l)=l/a[x-1]*S[x-1]+solve(x-1,l%a[x-1])。

我们发现，如果 l<a[x−1] ，这就直接等于solve(x-1,l)。

比起一个一个这样操作，如果我们每步都找到a[y]<=l的最大的y呢？

有一个经典性质，一个数每次模不大于它的数，只会模log次。

证明显然。

这样我们只会跳log步！

于是我们一定可以把S[i]表示成log个小于i的S[j]乘上一些系数的和，再加上一个边界的前缀。

那么不妨倒推，用cnt[i]表示S[i]在答案中计算次数，就可以递推到前面的cnt[j]。

最后把那些前缀系数标记到数组上，倒扫求和即可求出答案。

不太明白的可以看代码实现。

#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int maxn=100000+10,maxtot=maxn*25;
ll ans[maxn],cnt[maxn],a[maxn],b[maxn],tree[maxtot],p[maxn][70][2];
int root[maxn],left[maxtot],right[maxtot],rk[maxn];
int len[maxn];
int i,j,k,l,t,n,m,tot,top,num;
int newnode(int x){
    tree[++tot]=tree[x];
    left[tot]=left[x];
    right[tot]=right[x];
    return tot;
}
void insert(int &x,int l,int r,int a,int b){
    x=newnode(x);
    tree[x]=b;
    if (l==r) return;
    int mid=(l+r)/2;
    if (a<=mid) insert(left[x],l,mid,a,b);else insert(right[x],mid+1,r,a,b);
}
int query(int x,int l,int r,int a,int b){
    if (!x||a>b) return 0;
    if (l==a&&r==b) return tree[x];
    int mid=(l+r)/2;
    if (b<=mid) return query(left[x],l,mid,a,b);
    else if (a>mid) return query(right[x],mid+1,r,a,b);
    else return max(query(left[x],l,mid,a,mid),query(right[x],mid+1,r,mid+1,b));
}
void solve(int x,ll l){
    int t=upper_bound(b+1,b+num+1,l)-b-1;
    int y=query(root[x-1],1,num,1,t);
    if (!y){
        if (l>=n){
            p[i][++top][0]=0;
            p[i][top][1]=l/n;
            l%=n;
        }
        p[i][++top][0]=l;
        return;
    }
    p[i][++top][0]=y;
    p[i][top][1]=l/a[y];
    solve(y,l%a[y]);
}
int main(){
    scanf("%d%d",&n,&m);
    a[0]=n;
    fo(i,1,m) scanf("%lld",&a[i]),b[i]=a[i];
    //b[++m]=n;
    sort(b+1,b+m+1);
    num=unique(b+1,b+m+1)-b-1;
    b[++num]=2000000000000000000;
    fo(i,1,m) rk[i]=lower_bound(b+1,b+num+1,a[i])-b;
    fo(i,1,m){
        root[i]=root[i-1];
        insert(root[i],1,num,rk[i],i);
    }
    fo(i,1,m){
        top=0;
        solve(i,a[i]);
        len[i]=top;
    }
    cnt[m]=1;
    fd(i,m,1){
        fo(j,1,len[i]-1)
            cnt[p[i][j][0]]+=cnt[i]*p[i][j][1];
        ans[p[i][len[i]][0]]+=cnt[i];
    }
    ans[n]+=cnt[0];
    fd(i,n,1) ans[i]+=ans[i+1];
    fo(i,1,n) printf("%lld\n",ans[i]);
}