AT_agc003_e 题解

题目链接

神仙题，我会把我自己思考的过程一步步写出来。

初看这题时感觉没什么思路，所以随便算了点东西。很容易发现如果对于一个 $i$，$q_i\geq q_{i+1}$，那么 $q_i$ 就没有意义，每次把元素放进来时先把头部比它大的都弹走，再把它放进去，设处理完的 size 为 cnt。

然后就是这道题的精髓所在了！很容易就可以发现 $q_i+1$ 的串是 $q_i$ 串的弱循环。所以就可以弄一个 solve 函数，solve (x, y) 意思是处理第 $q$ 个串循环 $y$ 遍的贡献。运行 solve (cnt, 1) 就可以了，但是 solve 函数怎么设计呢？

以下设 $q_i=len_i$

前面的循环节可以用 solve (cnt - 1, len[cnt] / len[cnt - 1]) 处理，但是后面多余的呢？

这时我们发现需要改变 solve 函数了，设 solve (x, y) 为处理前 $x$ 个字符循环 $y$ 次的贡献。

转移首先要找到第一个 $t$，使得 $len[t] < x$，前面的部分仍然是循环，solve (len[t], x / len[t]) 就解决了，后面还有 $x$ $\bmod$ $len[t]$ 个剩余的，这些只循环 1 次，solve (x % len[t], 1) 就可以了。

另外，注意下边界问题，如果 $x\leq n$ 了，那么前 $x$ 个字符就是 $1\cdots x$，这些的出现次数都 $+1$，用差分维护就行。

分析一下时间复杂度，$T(x)= x + T(x - 1) + T (\frac{x}{2})=x^2$，考虑优化。

时间主要用在了 $x$ 和 $T(x-1)$ 上，第一个用二分可以 $\log_n$。关于第二个，solve 函数都是 solve (len[t], x / len[t]) 的形式，第一个参数也就 $n$ 种。因此，我们用一个桶 $f$，$f[t]$ 统计的是 $1$ 到 $len[t]$ 个字符循环的次数（即出现在最终字符串中的次数）。最后再把 $f$ 中的一起统计一下就行。

现在的 solve 函数就成了这样：

void solve (int x, int y) {
    if (x <= n) {
        d[1] += y;
        d[x + 1] -= y;
        return;
   }
   int t = lower_bound (len + 1, len + cnt + 1, x) - len - 1;
   f[t] += x / a[t] * y;
   solve (x % a[t], y);
}

结束后，我们倒序循环一下。$f[i]$ 拆成 $f[i - 1] * \lfloor\frac{len[i]}{len[i - 1]}\rfloor + len[i] $ $\bmod$ $len[i - 1]$，前面的加到 $f[i-1]$ 上，后面的继续用 solve 函数。（即 solve (len[i] % len[i - 1], f[i]) ）。

此题的 $q_i$ 也可能小于 $n$，所以遇到这种情况，我们把 $n$ 设为最小的 $q_i$，输出时 $>n$ 的输出 $0$ 即可。

这样，时间复杂度降到了 $n\log^2 n$，另外注意开长整型和特判 $q=0$ 的情况。

少量注释的代码：

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
int n, q, cnt;
int a[100005], d[100005], f[100005];
void solve (int x, int y) {//求解前 x 个字符的贡献乘上 y 
    if (x <= n) {
        d[1] += y;
        d[x + 1] -= y;
        return;
    }
    int t = lower_bound (a + 1, a + cnt + 1, x) - a - 1;
    f[t] += x / a[t] * y;//其实是前 a[t] 个字符乘上 x / a[t] 加上剩余的。 
    solve (x % a[t], y);
}
signed main () {
    int x, z;
    cin >> n >> q;
    if (q == 0) {
        for (int i = 1; i <= n; i ++) cout << 1 << "\n";
        return 0;
    }
    z = n;
    a[++ cnt] = n;
    for (int i = 1; i <= q; i ++) {
        cin >> x;
        n = min (n, x);
        while (cnt != 0 && a[cnt] >= x) -- cnt;
        a[++ cnt] = x;
    }
    solve (x, 1);
    for (int i = cnt; i >= 2; i --) {
        f[i - 1] += a[i] / a[i - 1] * f[i];
        solve (a[i] % a[i - 1], f[i]);
    }
    d[1] += f[1];
    d[n + 1] -= f[1];
    for (int i = 1; i <= n; i ++) {
        d[i] += d[i - 1];
        cout << d[i] << "\n";
    }
    for (int i = n + 1; i <= z; i ++) cout << 0 << "\n";
    return 0;
}