美味果凍

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

接下來(lái)只需要從小到大枚舉$i$，因?yàn)橛?span id="ze8trgl8bvbq" class="katex--inline">$j\in [ki,(k+1)i],?\frac{j}{i}?=k$，所以這里有一個(gè)分塊性質(zhì)，差分前綴和即可得到。

最后在得到的數(shù)組中乘上一個(gè)數(shù)組下標(biāo)，在求一次前綴和即是答案了。

#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; }

總結(jié)

以上是生活随笔為你收集整理的美味果冻（牛客练习赛53B）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。