b_mt_小团的装饰物（变形多重背包）

从左到右有m个空位需要放上装饰物。商店中每个整数价格的装饰物恰好有一种，且每种装饰物的数量无限多。
小团去商店的时候，想到了一个购买方案，他要让右边的装饰物价格是左边的倍数。用数学语言来说，假设小团的m个装饰物价格为a_1,a_2,...,a_m，那么对于任意的1≤i≤j≤m，a_j是a_i的倍数。小团是一个节约的人，他希望最贵的装饰物不超过n元。现在，请你计算小团有多少种购买的方案？

思路：f[i][j]表示第i个位置放j价值的装饰物时的方案数，f[i]只跟f[i-1]有关

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int limit, m; cin>>limit>>m;
    int f[m+5][limit+5]; memset(f,0,sizeof f);
    for (int i=1; i<=limit; i++) f[1][i]=1;
    for (int i=1; i<=m; i++)
    for (int j=1; j<=limit; j++)
    for (int c=1; c*j<=limit; c++) {
        f[i][j]=(f[i-1][c*j]+f[i][j])%mod;
    } 
    int ans=0;
    for (int j=1; j<=limit; j++)
        ans=(ans+f[m][j])%mod;
    cout<<ans;
    return 0;
}

b_mt_小团的装饰物（变形多重背包）

原文：https://www.cnblogs.com/wdt1/p/14509162.html