【题解】CF1854E Game Bundles

你考虑我们需要构造出一组解，显然地这样的解有很多很多种（\({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;
        }
	}
}