题解：AT_agc003_e [AGC003E] Sequential operations on Sequence

题目链接：[AGC003E] Sequential operations on Sequence

一道非常有思维含量的题目。

首先摒除无用操作：若 q_{i-1} >q_{i}，则可以把操作序列中的 q_{i-1} 删去。这样，操作序列变成了一个单调递增的序列。

考虑每一个操作后的序列长什么样：

对于每个一次操作 i，其操作后的序列一定形如：\left \lfloor \frac{q_{i}}{q_{i-1}} \right \rfloor 个长度操作 i-1 形成的序列 + 1 个操作 i-1 形成的序列的前 q_i \bmod q_{i-1} 个元素。

前面一段是重复的，只需要令 f_{i} 表示操作 i 形成的串在最终答案中重复了几次。易得转移：f_i=\left \lfloor \frac{q_{i+1}}{q_{i}} \right \rfloor\times f_{i+1}。

接下来考虑多余的部分如何计算。

设 w_{i} 表示第 i 次操作后多余部分的长度。

每次找到一个最大的 q_{j} 使得 q_{j} \le w_{i}，则多余部分形如：\left \lfloor \frac{w_{i}}{q_{j}} \right \rfloor 个长度操作 j 形成的序列 + 1 个操作 j 形成的序列的前 w_i \bmod q_{j} 个元素。

这样问题 i 又转化为了子问题 j，递归即可。

证明如下：

若 k\le \left \lceil \frac{w}{2} \right \rceil，则 w \bmod k < \left \lceil \frac{w}{2} \right \rceil（余数小于除数）。

若 \left \lceil \frac{w}{2} \right \rceil<k\le w，则 w \bmod k=w-k，而 w-k<\left \lceil \frac{w}{2} \right \rceil。

据此结论，可保证每次递归次数为 O\left(\log V\right)。

每次递归都要二分查找一个最大的 q_{j} 使得 q_{j} \le w_{i}，故时间复杂度为 O\left(n\log n\log V\right)。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, Q, q[100005], s[100005], top, d[100005], f[100005];

void solve(int x, int y)
{
    int t = upper_bound(s + 1, s + top + 1, x) - s - 1;
    if (!t)
    {
        d[1] += y;
        d[x + 1] -= y;
        return;
    }
    f[t] += (x / s[t]) * y;
    solve(x % s[t], y);
}

signed main()
{
    cin >> n >> Q;
    q[1] = n;
    Q++;
    for (int i = 2; i <= Q; i++)
        cin >> q[i];
    for (int i = 1; i <= Q; i++)
    {
        while (s[top] > q[i]) top--;
        s[++top] = q[i];
    }
    f[top] = 1;
    for (int i = top; i >= 2; i--)
    {
        solve(s[i] % s[i - 1], f[i]);
        f[i - 1] += (s[i] / s[i - 1]) * f[i];
    }
    d[1] += f[1];
    d[s[1] + 1] -= f[1];
    for (int i = 1; i <= n; i++)
    {
        d[i] += d[i - 1];
        cout << d[i] << endl;
    }
    return 0;
}