专栏文章

题解：P8189 [USACO22FEB] Redistributing Gifts G

MMarSer020
P8189题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mine11hs
此快照首次捕获于
2025/12/02 00:52
3 个月前
此快照最后确认于
2025/12/02 00:52
3 个月前
查看原文
怎么都不写哈集幂喵！怎么还有 O(3n)O(3^n) 喵！捅死你喵！捅死你喵！捅死你喵！捅死你喵！捅死你喵！捅死你喵！捅死你喵！捅死你喵！捅死你喵！
Solution\Large\text{Solution}
考虑先将题意转化，观察到要求交换后的优先嘟比交换前的优先嘟高，可以直接将当前的 ii 连向优先嘟比 ii 高的位置，最后相当于要将相同颜色的剖成若干个环，求方案数。
n≤18n\le18 考虑状压 dp，有一个比较正常的 dp 是先设 gS,ig_{S,i} 表示从 lowbit(S)\text{lowbit}(S) 出发，经过了 SS 中的点，到 ii 的方案数，hSh_S 表示 SS 中的点连成一个环的方案数，转移比较简单就不说了，这一部分是 O(2nn2)O(2^nn^2) 的。
然后我们设 fSf_S 表示将 SS 集合剖成若干个环的方案数，那么为了不重复计数可以钦定枚举包含 highbit(S)\text{highbit}(S) 的环进行计数。写出转移式就是：
fS=∑T⊆S[highbit(S)≠highbit(T)]fThS−Tf_S=\sum\limits_{T\subseteq S}[\text{highbit}(S)\neq\text{highbit}(T)]f_Th_{S-T}
那就随便做 O(3n)O(3^n) 了，好像还能过，但是你不准写这个做法。
考虑对这个 dp 进行优化。你发现去掉 [highbit(S)≠highbit(T)][\text{highbit}(S)\neq\text{highbit}(T)] 就是一个子集卷积板子。那你考虑先从小到大枚举 highbit(S)\text{highbit}(S) 的值然后每次都跑一遍子集卷积就可以了。你算一下复杂度是 ∑O(2ii2)=O(2nn2)\sum O(2^ii^2)=O(2^nn^2)，那么总时间复杂度就是 O(2nn2)O(2^nn^2) 了。
Code\Large\text{Code}
CPP
#include<bits/stdc++.h>
#define int int64_t
using namespace std;
int n,q,a[18][18],e[18][18],f[262144],h[262144],tmp[262144],S,g[262144][18];
string str;
namespace fwt{
	int f[1048576],g[1048576],h[1048576];
	void fwtor(int n,int*f,int mul){
		for(int i=1;i<1<<n;i<<=1)
			for(int j=0,p=i<<1;j<1<<n;j+=p)
				for(int k=0;k<i;k++)
					f[i+j+k]+=f[j+k]*mul;
	}
	void _or(int n,int*a,int*b,int*c){
		memcpy(f,a,(1<<n)*sizeof(a)),memcpy(g,b,(1<<n)*sizeof(b)),fwtor(n,f,1),fwtor(n,g,1);
		for(int i=0;i<1<<n;i++)
			h[i]=f[i]*g[i];
		fwtor(n,h,-1),memcpy(c,h,sizeof(h));
	}
}
namespace Subset{
	using namespace fwt;
	int f[19][262144],g[19][262144],h[19][262144];
	void subset(int n,int*a,int*b){
		memset(f,0,sizeof(f)),memset(g,0,sizeof(g)),memset(h,0,sizeof(h));
		for(int s=0,x;s<1<<n;s++)
			x=__builtin_popcount(s),f[x][s]=a[s],g[x][s]=b[s];
		for(int i=0;i<=n;i++){
			fwtor(n,f[i],1),fwtor(n,g[i],1);
			for(int j=0,k=i;j<=i;j++,k--)
				for(int s=0;s<1<<n;s++)
					h[i][s]+=f[j][s]*g[k][s];
			fwtor(n,h[i],-1);
		}
		for(int s=0;s<1<<n;s++)
			if(s>>(n-1)&1)
				a[s]=h[__builtin_popcount(s)][s];
	}
}
int32_t main(){
	ios::sync_with_stdio(0),cin.tie(0),cin>>n,f[0]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)
			cin>>a[i][j],a[i][j]--;
		for(int j=0;j<n;j++){
			if(a[i][j]==i)
				break;
			e[i][a[i][j]]=1;
		}
		h[1<<i]=g[1<<i][i]=1;
	}
	for(int s=1,p;s<1<<n;s++){
		p=__builtin_ctz(s);
		for(int i=p;i<n;i++)
			if(s>>i&1&&g[s][i]){
				if(e[i][p])
					h[s]+=g[s][i];
				for(int j=p+1;j<n;j++)
					if(!(s>>j&1)&&e[i][j])
						g[s|1<<j][j]+=g[s][i];
			}
	}
	for(int m=1;m<=n;m++)
		Subset::subset(m,f,h);
	cin>>q;
	while(q--){
		cin>>str,S=0;
		for(int i=0;i<n;i++)
			S|=(str[i]=='H')<<i;
		cout<<f[S]*f[S^((1<<n)-1)]<<'\n';
	}
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...