自动搬运

查看原文

来自洛谷，原作者为

	Grand_Dawn 小WA撑小艇，偷采AC回

搬运于2025-08-24 23:04:54，当前版本为作者最后更新于2024-04-03 16:06:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

mex1 题解

checker

解决该问题，知道如何写 checker 是必要的。

首先，如果 $a_i>n$，则可以直接令 $a_i\leftarrow n$，因为一个子集最多有 $n$ 个元素，$\text{mex}$ 最大为 $n-1$。

又可以发现相同的数字之间没有区别，所以可以设 $\text{calc}(n,cnt_0,cnt_1,\cdots,cnt_n)$ 表示所有子集 $\text{mex}$ 求和。

如果不选取 $0$，该部分答案显然为 $0$。

如果选取了至少一个 $0$，那么共有 $2^{cnt0}-1$ 种选取 $0$ 的方案。

而对于选取非 $0$ 的元素，$ans=\text{calc}(n-cnt_0,cnt_1,\cdots,cnt_n)$ 已经计算出所有这些元素 $-1$ 的子集 $\text{mex}$ 求和。

而且又有这些子集共有 $2^{n-cnt_0}$ 个。因此，答案为 $(ans+2^{n-cnt_0})(2^{cnt_0}-1)$。

因此可以在 $\Theta(n)$ 的时间复杂度内算出答案。

性质

显然以上的过程是唯一确定的，可以认为是一种递推过程。

即可以定义 $f(x,n)$ 表示用 $n$ 个元素凑成答案为 $x$ 是否存在解；如果存在解，则记录 $cnt_0$ 可能的值。直接枚举 $cnt_0$ 是否存在解。

递推式：$f(x,n)\overset{\text{or}}\leftarrow f(\frac{x}{2^i-1}-2^{n-i},n-i)$。

边界条件：

1. $f(0,n)=\textbf{true}$，此时需要填入 $n$ 个 $1$ 符合答案。

2. $x>0$ 时 $f(x,0)=\textbf{false}$。

3. $x<0$ 时 $f(x,n)=\textbf{false}$。

如果采用递推可以获得 $55$ 分。采取枚举 $n$ 后记忆化搜索可以获得 $60$ 分。

优化下界

可以发现很多记忆化数组中很多的答案都是 $\textbf{false}$，因此可以对于固定的 $n$ 可以找到 $x$ 的上下界使得 $f(x,n)\neq \textbf{false}$。

可以发现，当 $x<2^n$ 时，$f(x,n)\neq\textbf{false}$ 当且仅当 $x=2^n-2^k$（$k$ 为整数且 $0\le k\le n$），以下进行证明：

初始时先令 $a_i=n$，考虑从小到大填入真正的 $a_k$ 的过程，加入 $a_k$ 后，$\text{mex}=c(c\in \mathbb{Z})$ 的数量均为 $2^{n-k}$ 的倍数，在于剩下的 $n-k$ 个 $n$ 可以任意选择选与不选。

若加入 $a_k$ 时 $x$ 发生变化，则由以上性质得至少增加 $2^{n-k}$。

若加入 $a_k$ 时 $x$ 不变化，则 $a_k$ 数组中不存在 $a_k-1$，因此等价于之后均不会增加 $x$。

因此若加入 $a_k$ 之前每个元素均发生变化，则 $x$ 至少为 $\sum\limits_{i=1}^{k}2^{n-i}=2^n-2^k$。又由于是 $2^{n-k}$ 得倍数，且 $x<2^n$，故 $x=2^n-2^k$。

因此证明完毕，构造仅需采用 $k$ 个 $0$ 和 $n-k$ 个 $n$ 即可。

实际上，下界仅需要设定为 $2^{n-1}$ 就可以通过此题。

优化上界

可以发现有以下性质：如果 $x$ 取到上界，那么 $cnt_0\ge cnt_1\ge cnt_2\ge\cdots\ge cnt_n$。

证明：如果 $cnt_k<cnt_{k+1}$，那么对比交换 $cnt_k$ 和 $cnt_{k+1}$ 的结果：

那么对于 $c>k+1$ 的 $\text{mex}=c$ 的子集数量为 $\prod\limits_{i=1}^{c-1}(2^i-1)$，数量不变。

对于 $c\le k$ 的 $\text{mex}=c$ 的子集数量为 $\prod\limits_{i=1}^{c-1}(2^i-1)$，数量不变。

而 $\text{mex}=k+1$ 的子集数量 $\prod\limits_{i=1}^{k}(2^i-1)$，数量变多。

因此答案会变大。使用冒泡排序可证明以上性质。

因此使用拆分数暴力枚举可以确定上确界。

实际上，上界仅需要设定为 $n\cdot 2^{n-1}$（所有子集长度之和）就可以通过此题。上界设定为 $n\cdot 2^n$ 应该不能通过。

#include<bits/stdc++.h>
#define N 35
#define INF 2000000009
using namespace std;
void write(int x){
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
int pw[N],mx[N];
template<class first,class second,int C>
struct Unordered_map{
	struct node{
		first t;
		second w;
		int nxt;
	}e[C+9];
	int tot,hd[C+9];
	int hash(first x){
		return x%C;
	}
	second& operator [](first a){
		int x=hash(a);
		for(int i=hd[x];i;i=e[i].nxt){
			if(e[i].t==a)return e[i].w;
		}
		e[++tot].t=a;
		e[tot].nxt=hd[x];
		hd[x]=tot;
		return e[tot].w;
	}
	second find(first a){
		int x=hash(a);
		for(int i=hd[x];i;i=e[i].nxt){
			if(e[i].t==a)return e[i].w;
		}
		return -1;
	}
};
Unordered_map<int,char,300009>mp[N];
int check(int x,int n){
	if(x==0)return 1;
	if(x>mx[n])return 0;
	if(mp[n].find(x)!=-1)return mp[n][x];
	if(x<pw[n])return 0;
	for(int i=1;i<=n;i++){
		if(x%(pw[i]-1))continue;
		if(check(x/(pw[i]-1)-pw[n-i],n-i))return mp[n][x]=i;
	}
	return mp[n][x]=0;
}
void solve(){
	int x;cin>>x;
	for(int n=1;pw[n-1]<=x+1;n++)
		if(check(x,n)){
			int id=0;
			write(n);putchar('\n');
			while(x){
				int pos=mp[n][x];
				for(int i=pos;i>=1;i--)write(id),putchar(' ');
				x=x/(pw[pos]-1)-pw[n-pos];
				n-=pos;id++;
			}
			for(int i=n;i>=1;i--)write(id+1),putchar(' ');
			putchar('\n');
			return;
		}
	puts("-1");
}
int b[39];
int calc(){
	int c=0;while(b[c])c++;
	int ans=0,cnt=0;
	while(c>0){
		ans=(ans+pw[cnt])*(pw[b[--c]]-1);
		cnt+=b[c];
	}
	return ans;
}
int dfs(int x,int lft,int lst=1000000000){
	if(lft==0)return calc();
	int ans=0;
	for(int i=min(lft,lst);i>=1;i--){
		b[x]=i;
		ans=max(ans,dfs(x+1,lft-i,i));
		b[x]=0;
	}
	return ans;
}
int main(){
	//freopen("10-1.in","r",stdin);
	//freopen("a.out","w",stdout);
	pw[0]=1;for(int i=1;i<=31;i++)pw[i]=pw[i-1]*2;pw[32]=INF;
	for(int i=1;i<=31;i++){
		if(i<=28)mx[i]=dfs(0,i);
		else mx[i]=INF;
	}
	for(int i=1;i<=32;i++)
		for(int j=i-1,tmp=0;j>=0&&tmp<=INF;j--){
			tmp+=pw[j];
			mp[i][tmp]=i-j;
		}
	int t;cin>>t;
	while(t--)solve();
	return 0;
}