ToB企服应用市场:ToB评测及商务社交产业平台

标题: AtCoder Beginner Contest 313 [打印本页]

作者: 十念 时间: 2023-8-8 00:43
标题: AtCoder Beginner Contest 313
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;
}

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)