题解 | 小苯的前缀gcd构造

看到没有人想过dfs的解答，来一个相对比较好理解的dfs版本。

注意到n和m数据范围很小（50及以内），组数不超过10组，剪枝一下可以卡过时间。

注意到f(i)这个序列是不增序列，并且有 f(i+1) | f(i). 我们的目标是通过dfs搜索每一个位置的数。

怎么用dfs搜索构造序列呢？首先先预处理50以内的所有数字的因子，打表记录一下并降序排序所有的因子，在搜索开始前初始化一下因子表。接下来我们用pos表示当前枚举的位置，prev表示上一个元素的数值，sum表示当前已经选择的元素之和。显然，我们的x不能小于n（如果x=n，直接构造n个1）也不能大于n*m（如果x=n*m，直接构造n个m），如果x不满足那就不用构造，直接输出-1不可行。

接下来，我们dfs判断是否存在可行的构造。我们剩下n-pos个数字可以填充，如果是最小的情况，后面的所有数字都会是1，如果是最大的情况，当pos=0，所有的数字可以都是m，当pos不为0，所有的数字都是prev。我们先剪枝判断x在不在 [最小情况, 最大情况] 的区间中。

我们用curr表示当前的元素。首先，由于 f(i) 具有的性质，我们枚举curr是从prev的因子中从大到小枚举的。接下来就是剪枝，不难想对于后续的序列构造，我们有下界（后续元素全部都是1）和上界（后续元素全部都是curr） sum+curr+(rem−1)≤x≤sum+curr+(rem−1)×curr 解得：下界=⌈(x−sum)/rem⌉, 上界=x−sum−(rem−1)且 curr 必须满足 下界≤curr≤上界。若 下界 > 上界 我们同样剪枝；否则枚举 curr 时只会在这个区间枚举。代码如下

// Lang: cpp
// Auth: Hanzhi

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define lll __int128
#define endl '\n'
#define pll pair<long, long>
#define pii pair<int, int>
#define pb push_back
#define fst first
#define scd second
#define hajimi ios::sync_with_stdio(false),
#define nanbei cin.tie(nullptr),
#define lvdou cout.tie(nullptr);

int n,m,x;
vector<int> res;
vector<int> fac[51];

void init()
{
    for(int i=1;i<=50;i++)
    {
        for(int j=1;j<=i;j++)
        {
            if(i%j==0) fac[i].push_back(j);
        }
        sort(fac[i].rbegin(),fac[i].rend());
    }
}

bool dfs(int pos, int prev, int sum)
{
    int remind=n-pos;
    if(remind==0) return sum==x;
    int mnposs=sum+remind;
    int mxposs=sum+(pos==0?remind*m:remind*prev);
    if(x<mnposs||x>mxposs) return false;
    int l=(x-sum+remind-1)/remind;
    int h=x-sum-(remind-1);
    if(l>h) return false;
    if(pos==0)
    {
        int st=min(m,h);
        for(int cur=st;cur>=l;cur--)
        {
            res.push_back(cur);
            if(dfs(pos+1, cur, cur+sum)) return true;
            res.pop_back();
        }
    }
    else {
        for(auto cur:fac[prev])
        {
            if(cur<l) break;
            if(cur>h) continue;
            res.push_back(cur);
            if(dfs(pos+1, cur, sum+cur)) return true;
            res.pop_back();
        }
    }
    return false;
}

void solve(){
    cin>>n>>m>>x;
    if(x<n||x>n*m)
    {
        cout<<-1<<endl;
        return ;
    }
    res.clear();
    if(dfs(0, 0, 0))
    {
        for(auto i:res) cout<<i<<" ";
        cout<<endl;
    }
    else cout<<-1<<endl;
    return ;
}

int main(){
    hajimi nanbei lvdou
    int T=1;
    cin>>T;
    init();
    while(T--) solve();
    return 0;
}