自动搬运

查看原文

来自洛谷，原作者为

	Froggy 最初的一步，泪水之后再一次，雕刻的风景线，消逝在黄昏中的风，直到梦的最后。—— Clannad

搬运于2025-08-24 22:28:56，当前版本为作者最后更新于2021-02-10 10:43:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言：

感谢zyk对我的指导，我才得以写出这题。

2k 代码调了将近 3h 才调出来，看起来我的代码能力还需提高。

题解：

不难发现，一个满足条件的把集合排列好的排列，必须满足对于 $[1,m]$ 的每一种数，都存在一个区间，满足区间中的集合都包含这种数，并且区间外的集合都不包含这种数。

设 Solve(v,t) 考虑 $v$ 中这些集合，$t$ 中这些种类的数的方案数。$v$ 满足在最终排列中一定是连续的一段（即一定紧挨在一起）。

考虑找到一个 $t$ 的子集 $z$，使得 $v$ 中的数可以根据和 $z$ 的交集再划分成若干个必须挨在一起的集合的集合，然后答案乘上这些集合的集合的合法排列方案。

对于 $t$ 中数 $x$，设 $c_x$ 表示 $v$ 中包含 $x$ 的集合构成的集合。

考虑先找到那些不存在另一个数 $y$ 使得 $c_x\subset c_y$ 的集合 $x$。

如果直接按这些 $x$ 构成的 $z$ 划分集合，会 WA 一片。

拍一拍会发现问题出在有的数非常讨厌，比如一个数 $x$，虽然它会被某个 $c_y$ 包含，但是 $c_x$ 中存在两个集合使得这两个集合和 $z$ 的交集不同，如果 $x$ 不在 $z$ 中就 GG 了，所以需要把 $x$ 加进 $z$ 中。

具体如何统计答案建议自行思考。实现细节可以参考代码。

时间复杂度：$\mathcal{O}(nm^2)$。但是常数特别小，最慢点50ms。

code:

/*
zyk txdy zyk txdy
zyk txdy zyk txdy
zyk txdy zyk txdy
zyk txdy zyk txdy
zyk txdy zyk txdy
zyk txdy zyk txdy
zyk txdy zyk txdy
*/


const int mod=998244353;

int T,n,m,fac[N];
ull a[N];
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;++i){
		fac[i]=1LL*fac[i-1]*i%mod;
	}
}
struct Union_Set{
	int f[64],s[64];
	void init(int n){
		for(int i=0;i<n;++i)f[i]=i,s[i]=1;
	}
	int getf(int x){
		return f[x]==x?x:f[x]=getf(f[x]);
	}
	int Merge(int x,int y){
		int fx=getf(x),fy=getf(y);
		if(fx==fy)return 0;
		s[fx]+=s[fy],s[fy]=0;
		f[fy]=fx;
		return 1;
	}
};
int Solve(vector<ull> &p,ull t){
	ull z=0;
	static int cnt[64];
	memset(cnt,0,sizeof(cnt));
	bool same=true;
	for(int i=1;i<(int)p.size();++i){
		if(p[i]^p[0]){same=false;break;}
	}
	if(same)return fac[p.size()];
	for(auto x:p){
		for(int i=0;i<m;++i){
			if(x>>i&1)++cnt[i];
		}
	}
	for(int i=0;i<m;++i){
		if(t>>i&1){
			ull all=(1uLL<<m)-1;
			for(auto x:p){
				if(x>>i&1)all&=x;
			}
			bool ok=true;
			for(int j=0;j<m&&ok;++j){
				if(i==j||cnt[j]<cnt[i]||(cnt[j]==cnt[i]&&i<j))continue;
				if(all>>j&1){
					ok=false;break;
				}
			}
			if(ok)z|=1uLL<<i;
		}
	}
	while(true){
		bool qwq=false;
		for(int i=0;i<m;++i){
			if(t>>i&1&&!(z>>i&1)){
				ull tmp=~0uLL;
				for(auto x:p){
					if(x>>i&1){
						ull g=(x&z);
						if(~tmp&&tmp^g){
							z|=1uLL<<i;qwq=true;
							break;
						} 
						tmp=g;
					}
				}
			}
		}
		if(!qwq)break;
	}
	int res=1;
	map<ull,vector<ull> > mp;
	int rem=__builtin_popcountll(z);
	for(auto x:p){
		if(x){
			mp[x&z].push_back(x^(x&z));
		}
		else ++rem;
	}
	Union_Set S;
	S.init(m);
	for(auto [d,s]:mp){
		res=1LL*res*Solve(s,t^z)%mod;
		for(int i=0;i<m;++i){
			if(d>>i&1){
				for(int j=0;j<m;++j){
					if(d>>j&1)rem-=S.Merge(i,j);
				}
			}
		}
	}
	for(int i=0;i<m;++i){
		if(z>>i&1&&S.s[i]>1)(res<<=1)%=mod;
	}
	return 1LL*res*fac[rem]%mod;
}
int main(){
	init(100000);
	T=read();
	int cnt=0;
	while(T--){
		++cnt;
		n=read(),m=read();
		vector<ull> all;
		for(int i=1;i<=n;++i){
			all.push_back(read());
		}
		printf("%d\n",Solve(all,(1uLL<<m)-1));
	}
	return 0;
}