2024杭电多校3——1001深度自同构

一开始和队友想出来的式子, $p_{i}$ 是 $i$ 的因子数组 $an s [i] = \sum_{i = 1}^{k} an s [(i - p_{i}) / p_{i}]$ 一个 $O (n n)$ 的dp显然是过不了的然后想到了对每个数枚举倍数预处理因子的话计算的话,时间复杂度是 $O (n l nn)$ ,因为是 $\frac{n}{i} + \frac{n}{i + 1} + .... + \frac{n}{n}$ 约等于 $n l nn$ 发现还是TLE,STL常数太大了，队友突然想到可以直接算设当前数字是 $i$ ,枚举倍数 $j$ , $an s [i * j] + = an s [(i * j - j) / j] + = an s [i - 1]$ , $an s [i - 1]$ 已经算过了，可以进行转移,另外特殊处理因子是 $i$ 本身的情况， $+ 1$ 即可

文章插图一开始和队友想出来的式子, $p_{i}$ 是 $i$ 的因子数组 $an s [i] = \sum_{i = 1}^{k} an s [(i - p_{i}) / p_{i}]$ 一个 $O (n n)$ 的dp显然是过不了的然后想到了对每个数枚举倍数预处理因子的话计算的话,时间复杂度是 $O (n l nn)$ ,因为是 $\frac{n}{i} + \frac{n}{i + 1} + .... + \frac{n}{n}$ 约等于 $n l nn$ 发现还是TLE,STL常数太大了，队友突然想到可以直接算设当前数字是 $i$ ,枚举倍数 $j$ , $an s [i * j] + = an s [(i * j - j) / j] + = an s [i - 1]$ , $an s [i - 1]$ 已经算过了，可以进行转移,另外特殊处理因子是 $i$ 本身的情况， $+ 1$ 即可

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;
int n;
long long ans[1000100];
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i = 1;i<=1e6;++i){
        ans[i]+=1;
        for(int j = 1;j<=1e6/(i+1);++j){
            ans[(i+1)*j]=(ans[(i+1)*j]+ans[i])%mod;
        }
    }
    for(int i = 1;i<=n;++i) cout<<ans[i]%mod<<" ";
    return 0;
}

太菜啦QAQ,少用STL