数列递推（牛客练习赛83）（数学、分块）

数列递推

给定$f(0)$，定义$f_n=\sum _{i=1}^n{f}_{(n\mathrm{m}\mathrm{o}\mathrm{d}i)}$，求$f_1,f_2,f_3,\dots ,f_{n-1},f_n$。

$$\begin{gathered} \sum _{i=1}^n{f}_{(n\mathrm{m}\mathrm{o}\mathrm{d}i)} \\ \sum _{i=1}^n{f}_{(n-\frac{n}{i}i)} \end{gathered}$$

显然$\frac{n}{i}$具有分块性质，当$\frac{n}{i}$大于$\sqrt{n}$时，$i$只有$\sqrt{n}$个选择，可以直接枚举，

否则$\frac{n}{i}<\sqrt{n}$时，可以考虑$S_{i,j}=f_i+f_{i-j}+\dots$一个前缀和来转移。

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10, mod = 998244353;int f[N], s[N][310], n;inline int add(int x, int y) {return x + y < mod ? x + y : x + y - mod; }inline int sub(int x, int y) {return x >= y ? x - y : x - y + mod; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);scanf("%d %d", &n, &f[0]);for (int i = 1; i < 310; i++) {s[0][i] = f[0];}for (int i = 1; i <= n; i++) {for (int l = 1, r, k; l <= i; l = r + 1) {r = i / (i / l), k = i / l;if (k < 310) {int L = i - k * r, R = i - k * l;f[i] = add(f[i], s[R][k]);if (L > k) {f[i] = sub(f[i], s[L - k][k]);}}else {for (int j = l; j <= r; j++) {f[i] = add(f[i], f[i - k * j]);}}}for (int j = 1; j < 310; j++) {if (i >= j) {s[i][j] = add(s[i - j][j], f[i]);}else {s[i][j] = f[i];}}}for (int i = 1; i <= n; i++) {printf("%d%c", f[i], i == n ? '\n' : ' ');}return 0; }

总结

以上是生活随笔为你收集整理的数列递推（牛客练习赛83）（数学、分块）的全部内容，希望文章能够帮你解决所遇到的问题。

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