题解 | #D-数列递推#

数列递推

https://ac.nowcoder.com/acm/contest/11173/D

D题

$f_i=\sum_{j=1}^if_{(i\%j)}$

观察一下

$f_i=\sum_{j=1}^if_{(i\%j)}$
对于 $j$ 来说 $i \% j = i - k * j$
其中 $k = i / j$
会发现对于连续的 $j, j + 1, j + 2$ 中
会有一些数的 $k 相同 ! 所以可以用整除分块优化$
对于连续的相同的 $k$ 数来说，每多一个数对于 $i$ 的余数相当与减去 $k$
即是一段数的和而这一段数每一个之间差值为 $k$
$k$ 本身不会超过 $\sqrt{n}$ 所以可以开一个 $sum[i][j]$ 来记录前 $i$ 项每项之间差 $j$ 的前缀和
可以边求数边处理 $sum[i][j]$ 时间复杂度 $n\sqrt{n}$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod  = 998244353;
ll f[maxn], sum[600][maxn];
int K;
void solve(int pos) {
    // pos % a
    // = pos - k * a
    // k = pos / a;
    // 随着a的增加有一些数的k相同
    // 所以可以用整除分块优化 
    ll ans = 0;
    ans += f[0];
    for (int l = 2, r; l <= pos; l = r + 1) {
        r = pos / (pos / l);
        int k = pos / l;
        if (k > K) {
            ans = (ans + f[pos % l]);
            r = l;
            continue;
        }
        // 表示l~r 这一段的k 相同
        int ed = pos % l;
        int st = pos % r;
        if (st - k < 0) 
            ans = (ans + sum[k][ed]) % mod;
        else 
            ans = (ans + sum[k][ed] - sum[k][st - k]) % mod; 
    }
    f[pos] = ans;    
}

int main() {
    int n;
    cin >> n >> f[0];
    K = sqrt(n) + 1;
    int cnt = 0;
    for (int i = 1; i <= K; ++i) sum[i][0] = f[0];
    for (int i = 1; i <= n; ++i) {
        solve(i);
        cout << f[i] << ' ';
        for (int j = 1; j <= K; ++j) {
            if (i - j >= 0) sum[j][i] = (sum[j][i - j] + f[i]) % mod;
            else sum[j][i] = f[i];
        }
    }
    return 0;
}

补加：不是 $k$ 本身不会超过 $\sqrt{n}$ , 是当 $k$ 超过 $\sqrt{n}$ 的部分直接暴力最多只有 $\sqrt{n}$ 次
所以可以对于在 $k < \sqrt{n}$ 的部分进行分块，两个部分的时间总和不会超过 $n\sqrt{n}$ 当时写题解没说清...sorry.