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(rlogr)$$$ 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(rlogr)$$$? For each $$$x$$$ you are iterating through all number $$$xi \le r$$$ which is $$$r \sum_{i=l}^{i \le r} dp_{1/i} $$$ which is close to $$$O(rlogr)$$$ Thanks to NaimSS for correcting my time complexity.

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];
}
int 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.

Iterative DP by Farsh_LE:

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

Nearly same speed as recursive, a bit faster though.

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!