传送门
题意：给定n(2e5),m(2e5)，求长度为ｎ序列A的个数，其中是的整数倍，且不超过ｍ
dp[n][m]表示最后一个元素为n，长度为ｍ，元素互不相同,每个元素是前一个元素的整数倍(至少２倍)的序列个数,易知序列长度不会超过19
元素可以重复的情况等价于在不可重复的情况下乘上用隔板法把n个相同小球放入j个不同盒子且盒子非空的方案数,在上面方案数乘上即可
最终答案为
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
const int maxn = 2e5 + 5;
ll dp[maxn][22];
ll fac[maxn], inv[maxn];
ll n, m;
ll qpow(ll x, ll y)
{ll res = 1;while(y){if(y & 1) res = res * x % mod;x = x * x % mod;y >>= 1;}return res;
}
void init()
{fac[0] = 1;for(int i = 1; i <= 200000; ++i) fac[i] = i * fac[i - 1] % mod;inv[200000] = qpow(fac[200000], mod - 2);for(int i = 200000 - 1; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
}
ll C(ll n, ll m)
{if(n < m) return 0;return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main()
{cin >> n >> m;init();for(int i = 1; i <= m; ++i) dp[i][1] = 1;for(int i = 1; i <= 19; ++i){for(int j = 1; j <= m; ++j){for(int k = 2; k <= m; ++k){if(j * k > m) break;dp[j * k][i + 1] = (dp[j * k][i + 1] + dp[j][i]) % mod;}}}ll ans = 0;for(int i = 1; i <= m; ++i){for(int j = 1; j <= 19; ++j){ans = (ans + dp[i][j] * C(n - 1, j - 1) % mod) % mod;}}cout << ans << endl;
}