传送门

题意：给定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;
}