你考虑我们需要构造出一组解，显然地这样的解有很多很多种（\({60^{60}}\) 显然是及其地大）。
那关键是我们如何进行构造。
我们很容易知道每个集合里面 \(> 30\) 的数只有一个。
所以我们可以在 \([1,30]\) 中随机 \(a_i\)，直到满足的组数恰好小于等于 \(a_i\)，添加的时候维护数组 \(f_i\) 表示和为 \(i\) 的集合 \(S\) 的个数。
我们可以发现，有些时候小的 \(a_i\) 如果很多，那么我们的答案增涨速度会很快，所以我们可以进行一个优化，每次随机一个 \(len\)，然后让 \(a_i\) 在 \([1,len]\) 中随机。
然后我们最后差的答案怎么补上呢？我们显然可以在序列中添加 \(> 30\) 的数，添加 \(i\) 这个数，显然会让 \(f_{60} = f_{60} + f_{60-i}\) 然后我们按 \(f_{60-i}\) 从大到小加入 \(i\) 这个数即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN = 2e5 + 8;
mt19937 rnd(time(0));
int T,n,m;
ll a[NN],b[NN],p[NN];
ll f[NN];
int rdbt(int l,int r){return l + rnd() % (r-l+1);}
ll K,res;
int main(){
scanf("%lld",&K);
if(K <= 60){
printf("%lld\n",K);
for(int i = 1; i <= K; ++i) printf("60 ");
puts("");
return 0;
}
for(int i = 31; i <= 60; ++i) p[i] = i;
while(1){
for(int i = f[0] = 1; i <= 60; ++i) f[i] = 0;
int k = rdbt(1,29);
for(int i = 1; i <= n; ++i){
a[i] = rdbt(1,k);
if(f[60] + f[60-a[i]] > K){n=i-1;break;}
for(int j = 60; j >= a[i]; --j) f[j] += f[j-a[i]];
}
res = K - f[60];
sort(p+31 , p+61,[&](int x,int y){
return f[60-x]>f[60-y];
});
if(res < 0) assert(0);
for(int i = 31; i <= 60; ++i)
while(n < 60 && res >= f[60-p[i]]) res -= f[60-p[i]], a[++n] = p[i];
if(!res){
printf("%d\n",n);
for(int i = 1; i <= n; ++i) printf("%d ",a[i]);
puts("");
return 0;
}
}
}