Codeforces 1854E - Game Bundles

tzc_wk / 2023-08-12 / 原文

都这么会乱搞的吗/xia

随机生成若干 \(<30\) 的数直到它们当中和为 \(60\) 的子集个数 \(>k\) 为止。删去最后一个元素。然后考虑贪心确定 \(>30\) 的部分，具体方法是按照 \(dp_{60-x}\) 从大到小贪心选，如果剩余子集个数 \(\ge dp_{60-x}\) 就在序列中加入 \(x\)。如此随机化直到找到符合要求的序列为止。

证明的话不会，不过感性理解一下你随机出来的这个序列的 \(dp_{60-x}\) 应该近似于一个等比数列，有点类似于类比进制表示，所以你能随机出符合要求的序列的概率是很大的。

ll k;int ord[35],a[65];mt19937 rng(time(0));
int main(){
	scanf("%lld",&k);
	if(k<=60){printf("%lld\n",k);for(int i=1;i<=k;i++)printf("60 ");return 0;}
	for(int i=1;i<=30;i++)ord[i]=i+30;
	while(1){
		static ll dp[65];memset(dp,0,sizeof(dp));
		int lim=rng()%29+1,n=0;dp[0]=1;
		while(n<=60){
			n++;a[n]=rng()%lim+1;
			if(dp[60]+dp[60-a[n]]>k){--n;break;}
			for(int i=60;i>=a[n];i--)dp[i]+=dp[i-a[n]];
		}ll rk=k-dp[60];
		sort(ord+1,ord+31,[&](int x,int y){return dp[60-x]>dp[60-y];});
		for(int i=1;i<=30;i++)while(n<60&&rk>=dp[60-ord[i]])a[++n]=ord[i],rk-=dp[60-ord[i]];
		if(!rk){
			printf("%d\n",n);
			for(int i=1;i<=n;i++)printf("%d%c",a[i]," \n"[i==n]);
			return 0;
		}
	}
	return 0;
}