Wise Men[CF1326F]

发表于 2020-03-23 分类于 CF

题目链接

题意

有 $n$ 个人，告诉你这 $n$ 个人互相之间是否认识，然后将这 $n$ 个人排成一列，记为 $p_{i}$ ，设 $b_{i} = [p_{i} k n o w p_{i + 1}]$ ，对于 $b$ 的 $2^{n - 1}$ 种情况，求有多少个排列对应这种情况。

$n \leq 2^{18}$ 。

题解

这毒瘤数数题谁想得到啊。。

不过这种一般都能想到是容斥。难道真的是要比谁想象力丰富吗qwq

那就容斥吧。设 $f_{s}$ 表示当 $s$ 的第 $i$ 位为 $1$ 时， $i$ 和 $i + 1$ 必须认识，当 $s$ 的第 $i$ 位为 $0$ 时， $i$ 和 $i + 1$ 不必须认识。

那么最终的答案就是这个 $f$ 的超集和反演/高维差分。

这样子容斥的好处是，每一段 $1$ 之间的计算就不会受影响了。因为 $0$ 的条件变成了可以随便选。因此我们考虑每一个连续的段分开计算，最后再合并在一起。

而连续的 $k$ 个 $1$ 代表的是 $k + 1$ 个点，这些点相邻之间认识，所形成的一条链。

而这些连续段代表的节点个数加起来是 $n$ 。这显然是一个整数划分的形式，当 $n = 18$ 时为 $P_{18} = 385$ 。

也就是说我们实际上只需要考虑 $385$ 种情况即可。

设 $g_{s}$ 表示对于集合 $s$ 中的点，有多少种排列使得相邻之间认识，这个可以用状压DP算出。

那么对于整数划分 $\sum_{i = 1}^{k} x_{i} = n$ 而言，答案为 $\sum {|S_i|=x_i}[|\bigcup S_i|=n]\prod{i=1}^k g_{S_i}$。

这就很像WC2018的州区划分了。

设新的 $g_{i, s} = g_{s} \times [| s | = i]$ ，去掉其中一个限制。那么答案就是若干个 $g_{x_{i}}$ 做或卷积后对应位置相乘，然后再逆变换回来后的第 $2^{n} - 1$ 位。

显然 $g_{i}$ 可以预先FWT好。

可以发现，最后的IFWT只需要求的是其中一位。用子集反演稍微理解一下/死记硬背/找规律可以发现：

$I F W T_{A} [n] = \sum A_{i} \times (- 1)^{| n x o r i |}$

那么对于一个整数划分 $\sum_{i = 1}^{k} x_{i} = n$ ，就可以在 $O ((k + 1) 2^{n})$ 的时间内求出答案。

状压DP和预处理 $F W T_{g_{i}}$ 的时间都是 $O (n^{2} 2^{n})$ 的。

设 $n$ 的整数划分的个数总和为 $S_{n}$ ，则时间复杂度为 $O ((S_{n} + n^{2}) 2^{n})$ 。

当 $n = 18$ 时打表可得 $S_{18} = 1596$ 。CF时限4s，不慌不慌。

程序

#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl;
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int N=20;
const int M=(1<<19)+5;
int n,cnt,cnt2;
bool bo[N][N];
ll dp[M][N]; int num[M];
ll f[N][M],g[N][M],ans[M];
inline void fwt(ll *a,int n)
{
	for(int i=1;i<n;i<<=1)
		for(int j=0;j<n;j+=(i<<1))
			for(int k=0;k<i;k++)
				a[i+j+k]+=a[j+k];
}
inline void init()
{
	fo(i,1,cnt-1) num[i]=num[i-lowbit(i)]+1;
	fo(i,0,n-1) dp[1<<i][i]=1;
	fo(i,1,cnt-1)
		fo(j,0,n-1)
			if((1<<j)&i)
				fo(k,0,n-1)
					if((1<<k)&i)
						if(k!=j&&bo[k][j])
							dp[i][j]+=dp[i^(1<<j)][k];
	fo(i,0,cnt-1) fo(j,0,n-1) if((1<<j)&i) g[num[i]][i]+=dp[i][j];
	fo(i,1,n) fwt(g[i],cnt+1);
	f[0][0]=1; fwt(f[0],cnt+1);
}
int b[N],a[N],tot;
bool used[N];
vector<int> v;
void find(int k)
{
	if(k>tot)
	{
		int s=0,now=0;
		fo(i,1,tot)
		{
			fo(j,0,b[i]-2) s|=(1<<now),now++;
			now++;
		}
		v.pb(s);
		return;
	}
	fo(i,1,tot)
		if(!used[i])
			if(!(i&&a[i]==a[i-1]&&!used[i-1]))
			{
				used[i]=1;
				b[k]=a[i];
				find(k+1);
				b[k]=0;
				used[i]=0;
			}
}
inline void solve(int m)
{
	tot=m;
	v.clear(); find(1);

	ll sum=0;
	fo(i,0,cnt-1) sum+=f[m][i]*(((n-num[i])&1)?(-1):1);
	for(auto u:v) ans[u]=sum;
}
void dfs(int res,int top,int m)
{
	if(!res)return solve(top-1);
	fo(i,m,res)
	{
		Sum++;
		a[top]=i;
		fo(j,0,cnt-1) f[top][j]=f[top-1][j]*g[i][j];
		dfs(res-i,top+1,i);
	}
	a[top]=0;
}
int main()
{
	scanf("%d",&n); cnt=(1<<n); cnt2=1<<(n-1);
	char ss[20];
	fo(i,0,n-1)
	{
		//scanf("%s",ss);
		fo(j,0,n-1) bo[i][j]=ss[j]=='1';
	}
	init();
	dfs(n,1,1);
	DEBUG(Sum);
	fo(i,0,n-2)
		fo(j,0,cnt2-1)
			if(!(j>>i&1))
				ans[j]-=ans[j^(1<<i)];
	fo(i,0,cnt2-1) printf("%lld ",ans[i]);
	return 0;
}