【CF1326F2】Wise Men

【CF1326F2】Wise Men

Description

有\(n\)个人。给出\(n\)个人的「认识情况」(双向且保证合法)

定义bool值函数\(K(i,j)\)表示两个人是否认识

考虑一个\(n\)个人编号的排列\(p\)，定义其生成的\(01\)串\(\{s_{n-1}\}\)为\(\forall i\in[1,n-1]\cap\mathbb{Z_+},s_i=K(p_{i},p_{i+1})\)

统计对于\(2^{n-1}\)种不同的\(01\)串，有多少种排列可以生成它

Input

第一行一个数\(n\)

然后读入认识情况的矩阵

Output

一行\(2^{n-1}\)个数表示答案

Sample Input

3
011
101
110

Sample Output

0 0 0 6

Data Constraint

\(1\le n\le 18\)

Solution

首先可以做一个子集容斥，统计答案的后缀和

然后一个串中连续段形成了许多链，看起来我们要对\(2^{n-1}\)中子串算答案

但事实上若两个串的链长集合相等，它们的答案也是相等的

所以只用对\(n\)的分拆数算答案

在算答案的途中边加数边做子集卷积就可以了（可以发现，连续段之间的排列关系在这里已经计算过了）

由于我们只用求一项，所以不需要对整个做IFMT，直接用定义式计算即可

Code

#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define mo 998244353
#define LL long long
#define N 19

map<vector<int>,LL>id;
char ch[N];
int n,len,a[N][N],q[N],cnt,Count[1<<N];
LL g[1<<N][N],f[N][1<<N],tmp[N][1<<N],ans[1<<N];
vector<int>w;

void FMT(LL*A){
	F(i,0,n-1) for(int j=0;j<len;j+=(1<<i+1)){
		F(k,j,j+(1<<i)-1)A[k|(1<<i)]+=A[k];
	}
}

void dfs(int x,int lst){
	if(!x){
		LL sum=0;
		F(i,0,len-1)sum+=(n-Count[i]&1?-tmp[cnt][i]:tmp[cnt][i]);
		id[w]=sum;
		return;
	}
	F(i,lst,x){
		cnt++;
		w.push_back(i);
		F(j,0,len-1)tmp[cnt][j]=tmp[cnt-1][j]*f[i][j];
		dfs(x-i,i);
		w.pop_back();
		cnt--;
	}
}

int main(){
	scanf("%d",&n);
	len=1<<n;
	F(i,1,len-1)Count[i]=Count[i>>1]+(i&1);
	F(i,1,n){
		scanf("%s",ch+1);
		F(j,1,n)a[i][j]=ch[j]-'0';
	}
	F(i,0,(1<<n)-1)tmp[0][i]=1;
	F(i,1,n)g[1<<i-1][i]=1;
	F(S,0,(1<<n)-1) F(i,1,n)if(g[S][i]){
		F(j,1,n)if(!((1<<j-1)&S)&&a[i][j])g[S|(1<<j-1)][j]+=g[S][i];
	}
	F(S,0,(1<<n)-1) F(i,1,n)f[Count[S]][S]+=g[S][i];
	F(i,0,n)FMT(f[i]);
	dfs(n,1);
	F(S,0,(1<<n-1)-1){
		F(i,1,n-1)q[i]=(S&(1<<i-1)?1:0);
		w.clear();
		int tn=n;
		F(i,1,n-1)if(q[i]==1){
			int j=i;
			while(q[j+1]==q[j])j++;
			w.push_back(j-i+1+1);
			tn-=j-i+1+1;
			i=j;
		}
		F(i,1,tn)w.push_back(1);
		sort(w.begin(),w.end());
		ans[S]=id[w];
	}
	F(i,0,n-2) F(j,0,(1<<n-1)-1)if(!((1<<i)&j))ans[j]-=ans[j|(1<<i)];
	F(S,0,(1<<n-1)-1)printf("%lld ",ans[S]);
	return 0;
}