Hello Codeforces! So my friend Haidora thought that in problem C yesterday it asked for the number of beautiful sets of all lengths (lol) and we were talking now about a solution for this problem and came up with an $$$O(nloglogn)$$$ DP solution.

Formal Statement

A set of positive integers $$$S$$$ is called beautiful if, for every two integers $$$x$$$ and $$$y$$$ from this set, either $$$x$$$ divides $$$y$$$ or $$$y$$$ divides $$$x$$$ (or both).

You are given two integers $$$l$$$ and $$$r$$$ . Consider all beautiful sets consisting of integers not less than $$$l$$$ and not greater than $$$r$$$: You have to print their number modulo $$$998244353$$$

Solution

Let $$$dp_x$$$ be the number of beautiful sets we can build such that the minimum number in these sets is $$$x$$$. Now, how do we find $$$dp_x$$$? Let's iterate through all numbers $$$i$$$ such that $$$xi \le r$$$, which means that we'll go through all multiples of $$$x$$$ as long as they are less than $$$r$$$. Now let's add their answers to our $$$dp_x$$$. Formally:

$$$dp_x = 1 + \sum_{i=2}^{xi \le r} dp_{xi} $$$ Now our answer would be summing them all up, because we want all sets, so for all possible minimums we want to know the number of sets possible using it. Formally: $$$ans = \sum_{i=l}^{i \le r} dp_{i} $$$

Note that the $$$1+$$$ is there because choosing $$$x$$$ alone in a set is also valid.

Time complexity

Why is it $$$O(nloglogn)$$$? Well I'm not exactly sure how to prove this, but the solution is very similar to the Sieve of Eratosthenes. For each number, go through all of its multiples as long as they are less than some bound. So you can read proof of time complexity of Sieve of Eratosthenes I guess.

Implementation

I used recursive DP:

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+5,M=998244353;
int dp[N],l,r;
int rec(int x){
    if (x>r) return 0;
    if (dp[x]) return dp[x];
    dp[x]=1;
    for (int i=2;i*x<=r;i++) dp[x]=(dp[x]+rec(x*i))%M;
    return dp[x];
}
int32 main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>l>>r;
    int ans=0;
    for (int i=l;i<=r;i++) ans=(ans+rec(i))%M;
    cout<<ans<<endl;
    return 0;
}

This code runs less than 100ms on C++20(64) when $$$l = 1$$$ and $$$r = 10^6$$$ , and less than 2000ms when $$$l = 1$$$ and $$$r = 10^7$$$. Tried on Codeforces custom test.

Final Notes

This is my first blog of this kind, so feel free to share your opinions as it will help me and others for the future. Also, please point out any mistakes you find. And I have a few questions: Could there be a faster solution? Also if there is an iterative DP solution please share it, because I couldn't find any way to do it iteratively. Thanks!