题解 | #小苯的前缀gcd构造#

以下是详细注释帮助理解版

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()
#define vec1(T, name, n, val) vector<T> name(n, val)
#define vec2(T, name, n, m, val) vector<vector<T>> name(n, vector<T>(m, val))
#define vec3(T, name, n, m, k, val) vector<vector<vector<T>>> name(n, vector<vector<T>>(m, vector<T>(k, val)))
#define vec4(T, name, n, m, k, p, val) vector<vector<vector<vector<T>>>> name((n), vector<vector<vector<T>>>((m), vector<vector<T>>((k), vector<T>((p), (val)))))

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 2e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};
const int hx[] = {-2, -2, -1, -1, 1, 1, 2, 2}, hy[] = {-1, 1, -2, 2, -2, 2, -1, 1};

istream& operator>>(istream& is, i128& val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char& c : str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream& operator<<(ostream& os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

LL qpow(LL a, LL b) {
    LL ans = 1;
    a %= MOD;
    while (b) {
        if (b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

void solve() {
    int n, m, x;
    cin >> n >> m >> x;

    // 最小值是1, 那么数组的和不能低于n, 最大值同理
    if (x < n || x > n * m) {
        cout << -1 << '\n';
        return;
    }

    // 前缀 gcd 序列单调不增并且注意到f[i + 1]一定是f[i]的因子, 因此先处理因子表
    vector<vector<int>> d(m + 1);
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= i; ++j) {
            if (i % j == 0) {
                d[i].push_back(j);
            }
        }
    }

    // 定义状态表示f[j][k]为当前位置填j 总和是 k 是否是可行的, 用滚动数组优化
    vec2(int, f, m + 1, x + 1, 0);
    vec2(int, nxt, m + 1, x + 1, 0);
    // fa 记录当前状态是由哪一个因子转移过来的
    vec3(int, fa, n + 1, m + 1, x + 1, -1);

    // 初始化dp
    for (int i = 1; i <= m; ++i) {
        if (i <= x) {
            f[i][i] = 1;
            fa[1][i][i] = 0;
        }
    }

    // 长度 len 转移到len + 1
    for (int len = 1; len < n; ++len) {
        for (int i = 1; i <= m; ++i) {
            for (int sm = 1; sm <= x; ++sm) {
                if (!f[i][sm]) continue;
                for (int k : d[i]) {
                    int ns = k + sm;
                    if (ns <= x && !nxt[k][ns]) {
                        nxt[k][ns] = 1;
                        fa[len + 1][k][ns] = i;
                    }
                }
            }
        }
        f = nxt;
        for (int i = 1; i <= m; ++i) fill(all(nxt[i]), 0);
    }

    // 找到可能存在数组的和为x 的位置
    int v = -1;
    for (int i = 1; i <= m; ++i) {
        if (f[i][x]) {
            v = i;
            break;
        }
    }


    if (v == -1) {
        cout << -1 << '\n';
        return;
    }

    // 状态回溯求方案
    vector<int> ans(n + 1);
    int sm = x;
    for (int len = n; len >= 1; --len) {
        ans[len] = v;
        if (len > 1) {
            int pre = fa[len][v][sm];
            sm -= v;
            v = pre;
        }
    }

    for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
    cout << '\n';

/**/ #ifdef LOCAL
    cout << flush;
/**/ #endif
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}

代码思路主要参考AliLexiWalker, Orz