Yijan's Blog HomeArchives
6.18 模拟赛 A

我们考虑把输入的矩阵看成邻接矩阵，于是相当于是给了个图。

然后考虑询问，1 的位置就相当于前后有边相连，0 的位置就相当于没有边。于是相当于通过 1 分成了很多个联通块，这些联通块之间不能有边，求可以满足这个条件的排列个数。

这个不好求，我们考虑求钦定了某些位置有边，剩下无限制的方案数量，最后做一次逆与卷积即可。因为设 $F[s]$ 表示钦定了 $s$ 集合的 $1$ 的位置有边，剩下无限制的方案数量，$f[s]$ 表示恰好只有 $s$ 的 $1$ 的位置有边的方案数量。我们显然有

这个明显就是与卷积的 FWT，所以如果求出了 $F$ 只需要对其求 逆与 FWT 即可求出答案数组，做到 $O(1)$ 询问。

由于钦定了某些位置有边，相当于是把 $n$ 个点分成了很多个联通块，我们需要满足的是联通块内部是个链，联通块之间没有限制。于是我们可以枚举所有边的状态（一共 $2^{n-1}$ 种），每种状态中 $1$ 表示相邻两个点一定有边，否则表示没有限制。我们考虑拆成联通块大小是 $a_1,a_2,\dots a_x$ ，怎么去计算填排列的方案。相当于我们有 $1\sim n$ 的每个数，我们要把它们拆成很多份，每份内部都可以构成一条链。

我们可以算出 $f[l][sta]$ 表示点的状态为 $sta$ ，点的个数（也就是 $sta$ 的 $1$ 的个数）为 $i$ 的链的方案数量。具体计算是考虑 $dp[i][sta]$ 表示结尾为 $i$ ，状态为 $sta$ 的方案数量，直接 $dp$ 一下，然后加到 $f[popcount(sta)][sta]$ 里面即可。这里的复杂度是 $O(n^22^n)$ 的。

回到刚刚的问题，我们相当于是要做一个子集卷积的过程。但是注意到我们拆成的联通块大小的和是 $n$ ，而且我们最终只需要占满 $n$ 个点的方案，所以可以直接对 $f[a_1],f[a_2],\dots,f[a_x]$ 做一次或卷积即可。 可以给 $f[i]$ 提前做好 FWT，这样就只需要点积乘起来，最后对乘起来的东西 IFWT 回去即可，这样做这个的复杂度就只是 $n2^n$。

枚举边的方案是 $2^{n-1}$ ，这样整复杂度是 $n2^{2n-1}$ ，显然会爆炸。

这个时候可以注意到在做后面的东西的时候，联通块的顺序是没有关系的，因为联通块之间不存在限制。而且注意到 $17$ 的拆分不到 $300$ ，所以我们直接枚举拆分，对于拆分做前面所说的那个过程即可。

于是枚举 $2^{n-1}$ 的边集的过程中我们可以直接调用每种拆分预处理好的数组的值就可以了。

我实现的复杂度是 $O(n^22^n + 300 n2^n + 2^{n-1} n\log n )$ 。最后的 $\log$ 是对拆出的联通块大小排序从而确定这种边集对应着哪个拆法。由于这个题的操作常数都很小，所以跑的很快。

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
113
114
115
116
117
118
119
120
121
122
123
124
125
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 18
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , q;

void IFWTand( ll* A , int len ) {
	for( int mid = 1 ; mid < len ; mid <<= 1 )
		for( int i = 0 ; i < len ; i += ( mid << 1 ) )
			for( int j = 0 ; j < mid ; ++ j )
				( A[i + j] -= A[i + j + mid] );
}

void FWTor( ll* A , int len ) {
	for( int mid = 1 ; mid < len ; mid <<= 1 )
		for( int i = 0 ; i < len ; i += ( mid << 1 ) )
			for( int j = 0 ; j < mid ; ++ j )
				A[i + j + mid] += A[i + j];
}

void IFWTor( ll* A , int len ) {
	for( int mid = 1 ; mid < len ; mid <<= 1 )
		for( int i = 0 ; i < len ; i += ( mid << 1 ) )
			for( int j = 0 ; j < mid ; ++ j )
				A[i + j + mid] -= A[i + j];
}

int G[MAXN][MAXN] , A[MAXN];
char ch[MAXN];
ll dp[MAXN][( 1 << 17 ) + 6]; // dp[i][j] : number of paths end on i and pass state j
ll pd[MAXN][( 1 << 17 ) + 6];
ll S[( 1 << 17 ) + 6]; // S[i] : division is i , number of ways
int bc[MAXN] , cnt;
ll F[300][( 1 << 17 ) + 6];

int getit( vi& a ) { // a sorted
	int cur = n , ret = 0;
	for( int i = a.size() - 1 ; i >= 0 ; -- i ) {
		while( cur > a[i] ) -- cur , ret <<= 1;
		ret = ret << 1 | 1;
	}
	while( cur > 0 ) -- cur , ret <<= 1;
	return ret;
}

vi dv;
void dfs( int x , int pre ) {
	if( !x ) {
		int idx = getit( dv );
		bc[idx] = ++ cnt;
		rep( i , 0 , ( 1 << n ) - 1 ) F[cnt][i] = 1;
		for( int l : dv )
			rep( i , 0 , ( 1 << n ) - 1 ) F[cnt][i] = F[cnt][i] * pd[l][i];
		IFWTor( F[cnt] , ( 1 << n ) );
		return;
	}
	if( x < pre ) return;
	for( int i = pre ; i <= x ; ++ i )
		dv.pb( i ) , dfs( x - i , i ) , dv.pop_back( );
}

ll s[( 1 << 16 ) + 6];

void solve() {
	cin >> n;
	rep( i , 1 , n ) {
		scanf("%s",ch + 1);
		rep( j , 1 , n ) G[i][j] = ch[j] - '0';
	}
	rep( i , 1 , n ) dp[i][1 << i - 1] = 1;
	rep( sta , 1 , ( 1 << n ) - 2 )
		rep( i , 1 , n ) if( ( sta & ( 1 << i - 1 ) ) && dp[i][sta] )
			rep( j , 1 , n ) if( ( ~sta & ( 1 << j - 1 ) ) && G[i][j] )
				dp[j][sta | ( 1 << j - 1 )] += dp[i][sta];
	rep( i , 0 , ( 1 << n ) - 1 )
		rep( j , 1 , n ) pd[__builtin_popcount( i )][i] += dp[j][i];
	rep( i , 1 , n ) FWTor( pd[i] , ( 1 << n ) );
	dfs( n , 1 );
	rep( sta , 0 , ( 1 << n - 1 ) - 1 ) {
		dv.clear() , dv.pb( 1 );
		rep( i , 1 , n - 1 ) {
			if( sta & ( 1 << i - 1 ) ) ++ dv.back();
			else dv.pb( 1 );
		}
		sort( all( dv ) );
		int idx = getit( dv );
		s[sta] = F[bc[idx]][( 1 << n ) - 1];
	}
	IFWTand( s , ( 1 << n - 1 ) );
	cin >> q;
	int re;
	rep( i , 1 , q ) {
		re = 0;
		scanf("%s",ch + 1);
		rep( j , 1 , n - 1 ) re |= ( ch[n - j] - '0' << j - 1 );
		printf("%lld\n",s[re]);
	}
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}
文章作者: yijan
文章链接: https://yijan.co/618-mo-ni-sai-a/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog！