题解 | 小苯的前缀gcd构造喵～

你们都是可爱的小萝莉和小男娘喵～

显然发现只要前面被后面整除， 喵，并且如果答案存在一定可以构造这样的序列喵～

表示前 i 个最后一个数为 j 总和为 k 是否可能，直接转移就可以了喵～下标可以枚举因子优化喵～

发现转移是平移，于是可以用 bitset 优化喵～最终时间复杂度 喵～

#include <bitset>
#include <iostream>
#include <vector>
using namespace std;

vector<vector<bitset<2501>>> dp;
vector<int> res;

int n;
int m;
int x;

void Solve() {
    cin >> n >> m >> x;
    dp.assign(n, vector<bitset<2501>>(m + 1));
    for (int i = 1; i <= m; i++) {
        dp[0][i].set(i);
    }
    for (int i = 1; i < n; i++) {
        for (int r = 1; r <= m; r++) {
            for (int l = r; l <= m; l += r) {
                dp[i][r] |= dp[i - 1][l] << r;
            }
        }
    }
    int last = 1;
    res.resize(n);
    for (int i = n - 1; i > -1; i--) {
        bool flag = true;
        for (int j = last; j <= m; j += last) {
            if (dp[i][j][x]) {
                flag = false;
                res[i] = j;
                last = j;
                x -= j;
                break;
            }
        }
        if (flag) {
            cout << "-1\n";
            return;
        }
    }
    for (const auto& x : res) {
        cout << x << ' ';
    }
    cout << '\n';
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        Solve();
    }
}
// 64 位输出请用 printf("%lld")