AT_abc313_g

Crane_w · 2023-08-07 14:16:34 · 题解

G - Redistribution of Piles

题意翻译：

给定一个数列 a_i(a_i>0, i\in[1,n])，和一个数 s（初值为0），有两种操作：

A - 全局非零数减一，减去的和加到 s
B - 如果 s\ge n , s \leftarrow (s-n) 数列全局加一

题解

不妨先排个序,设 a_i\le a_{i+1}。

那么，每次操作 A, 一定是前面的数先变为零。那么我们考虑什么时候对答案的贡献会增加，

如果执行 A，再执行 B, 其间没有数值改变，那么这两次操作作废。

换句话说，我们仅仅执行有用的 A，B 操作。什么时候有用？

执行 A,当前状态未到达过。
执行 B,当前的数组差分情况刚刚发生改变。

那么全部有效的执行操作序列是形如“AAAABBB”（前缀为 A,后缀为 B）。

显然，有效的操作序列与最终序列形成双射。

考虑 A 操作执行到把 a_i 变为零，接着又把 a_{i+1}-1，即 (a_i,a_{i+1}] 。

那么当前可执行的 B 操作次数为：

\sum_{k=1}^{a_{i+1}-a_i} \lfloor\frac{s + k\cdot(n -i)}{n}\rfloor

直接做的复杂度 O(nA_{max})。

我们考虑优化，注意到上面的式子相当于数一个线段(分子形如 kx+b)下的点(x, dn)。

我们换一个角度看问题，我们求出每一个 kn 上面，有多少个点。

可以得到：

\sum_{k\in(0,N]} \lfloor\frac{a + dk}{m}\rfloor = \sum_{k\in(0,\lfloor \frac{dN+a}{m} \rfloor]} \lfloor\frac{(a+dN)\mod m + km}{d}\rfloor

我们递归求解即可,函数如下。

int solve(int N, int D, int A, int M) {
    if (!N) return 0;
    ll p = ((D / M) * (N * (N - 1) / 2) % mod + (A / M) * N % mod) % mod;
    D %= M, A %= M;
    if (D) add(p, solve((D * N + A) / M, M, (A + D * N) % M, D), mod);
    return p;
}