Wise Men[CF1326F]

发表于 分类于

题目链接

F1

F2

题意

有 $n$ 个人，告诉你这 $n$ 个人互相之间是否认识，然后将这 $n$ 个人排成一列，记为 $p_i$，设 $b_i=[p_{i}\ know \ 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}^kx_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只需要求的是其中一位。用子集反演稍微理解一下/死记硬背/找规律可以发现：

$IFWT_A[n]=\sum A_i\times (-1)^{|n\ xor\ i|}$

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

状压DP和预处理 $FWT_{g_i}$ 的时间都是 $O(n^22^n)$ 的。

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

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

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#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;
}