AtCoder Beginner Contest 313
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;
- }
|
