【题解】Atcoder AGC#03 E-Sequential operations on Sequence

　　仙题膜拜系列...首先我们可以发现：如果在截取了一段大的区间之后再截取一段小的区间，显然是没有什么用的。所以我们可以将操作序列变成单调递增的序列。

　　然后怎么考虑呢？启示：不一定要考虑每一个数字出现的次数——我们还可以计算每一段完整的序列出现的次数。如果我们求出第 \(i\) 次操作过后产生的序列在答案中共出现了 \(rec[i]\) 次，那么第 \(i - 1\) 次操作过后产生的序列必然在答案中出现了 \(\frac{len[i]}{len[i - 1]} * rec[i]\) 次。可是这样还会剩下\(rec[i]\) 段 \(len[i] \ mod \ len[i - 1]\) 的小区间。我们可以考虑如何统计这一段小区间中出现了哪些完整的序列。

　　由于要统计在这段小区间中出现了哪些完整的序列，我们可以找到操作序列中第一个长度小于它的位置\(pos\)。那么此时这段小区间中会有 \(\frac{nowlen}{len[pos]}\) 段长度为 \(len[pos]\) 的完整区间。显然这是一个递归求解的问题，而一个数最多取模 log 次的性质保证我们最多会递归 log 次。如果最后剩下的区间比第一个小区间还要小，那么我们可以直接知道对于那些数字的出现做出了贡献，维护差分序列区间加一下就好了。

　　**启示：可以转化一下思路，不一定要计算每个数字的贡献，而可以从后往前递推出每段序列出现的次数，将一段序列看作一个整体。而一个数取模最多不会超过 log 次的限制也可以保证递归的次数。

#include <bits/stdc++.h>

using namespace std;

#define maxn 1000000

#define int long long

int n, Q, m;

int rec[maxn], len[maxn], ans[maxn]; 

int read()

{

    int x = , k = ;

    char c; c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

void Solve(int x, int t)

{

    if(!x) return;

    int pos = upper_bound(len + , len +  + m, x) - len - ;

    if(!pos) { ans[] += t; ans[x + ] -= t; }

    else

    {

        rec[pos] += (x / len[pos]) * t;

        Solve(x % len[pos], t);

    }

}

signed main()

{

    n = read(), Q = read(); len[++ m] = n;

    for(int i = ; i <= Q; i ++)

    {

        int x = read();

        while(m && len[m] >= x) m --;

        len[++ m] = x;

    }

    rec[m] = ;

    for(int i = m; i > ; i --)

    {

        rec[i - ] += rec[i] * (len[i] / len[i - ]);

        Solve(len[i] % len[i - ], rec[i]);

    }

    ans[] += rec[], ans[len[] + ] -= rec[];

    for(int i = ; i <= n; i ++)

    {

        ans[i] += ans[i - ];

        printf("%lld ", ans[i]);

    }

    return ;

}

巴特西

【题解】Atcoder AGC#03 E-Sequential operations on Sequence

最新文章

热门文章