Hello Codeforces! So my friend [user:Anti_tourist4000,2023-03-01] 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(nrloglognr)$ 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(nrloglognr)$?↵
Well I'm notFor 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 ah $x$ you are iterating through all number $xi \le r$ which is $r \sum_{i=l}^{i \le r} dp_{1/i} $ which is clong as they are less than some bound. So you can read proof of time complexity of Sieve of Eratosthenes I guessse to $O(rlogr)$ Thanks to [user:NaimSS,2023-03-03] 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 [user:IOI_NEXT_CENTURY,2023-03-03]:↵
↵
~~~~~↵
#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!↵
↵
↵
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(
↵
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 [user:IOI_NEXT_CENTURY,2023-03-03]:↵
↵
~~~~~↵
#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!↵
↵
↵
