美味果冻（牛客练习赛53B）

美味果冻

$$\begin{gathered} \sum _{i=1}^n\sum _{j=1}^{i}i\times \lfloor \frac{i}{j}{\rfloor }^j \\ \sum _{i=1}^n\sum _{j=i}^{n}j\times \lfloor \frac{j}{i}{\rfloor }^i \end{gathered}$$

接下来只需要从小到大枚举$i$，因为有$j\in [ki,(k+1)i],\lfloor \frac{j}{i}\rfloor =k$，所以这里有一个分块性质，差分前缀和即可得到。

最后在得到的数组中乘上一个数组下标，在求一次前缀和即是答案了。

#include <bits/stdc++.h>using namespace std;const int N = 3e6 + 10, mod = 1e9 + 7;int f[N], g[N], n;void init() {for (int i = 1; i < N; i++) {g[i] = 1;}for (int i = 1; i < N; i++) {for (int j = i; j < N; j += i) {int l = j, r = j + i;g[j / i] = 1ll * g[j / i] * (j / i) % mod;int cur = g[j / i];f[l] = (f[l] + cur) % mod;if (r < N) f[r] = (f[r] - cur + mod) % mod;}}for (int i = 1; i < N; i++) {f[i] = (f[i - 1] + f[i]) % mod;} }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);init();scanf("%d", &n);int ans = 0;for (int i = 1; i <= n; i++) {ans = (ans + 1ll * i * f[i] % mod) % mod;}printf("%d\n", ans);return 0; }

总结

以上是生活随笔为你收集整理的美味果冻（牛客练习赛53B）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。