Petrozavodsk Winter Training Camp 2016F题Data Structure You’ve Never Heard Of

Problem

给定$n$个$d$维01向量序列$a_1,a_2…a_n$，求不下降子序列的个数（对$10^9+7$取模）。

Data Range

$1\leq n \leq 2\times10^5$

$1\leq d\leq 16$

Input & Output

Input	Output
4 3 110 100 011 101	5

所有的不下降子序列：[110]、[100]、[011]、[101]、[100, 101]

Solution

暴力算法1

这题也很容易想到动态规划，$dp[i]$表示以第$i$个数结尾的子序列个数。于是有$dp[i] = \sum_{j = 1}^{i -1}dp[j]\cdot(a[j] \in a[i])$。

时间复杂度：$O(n ^ 2)$

暴力算法2

或者也可以这样动态规划：$dp[i][j]$表示前$i$个数中以向量$j$为结尾的数的个数，将第一维滚掉，循环中对于第$i$个数$a[i]$，枚举$a[i]$的所有子集$j$，统计所有$dp[j]$的值计入答案，再更新$dp[a[i]]$。

暴力的时间复杂度：$O(n\cdot 2^d)$。

分块算法

可以发现暴力算法1的瓶颈在于每次要枚举前面所有的数很浪费时间，暴力算法2的瓶颈在于每次对于$a[i]$需要枚举所有子集，浪费了时间。

有没有什么办法可以结合两个暴力算法，打破各自的瓶颈？于是可以想到通过分块的思想减少枚举数与子集的次数。

用$dp[i]$表示以第$i$个数为结尾的不下降子序列个数，我们将原序列按每$B$个数，分成一块。对于同一个块内的转移可以直接通过暴力算法1的方法转移。对于不同块的转移，我们在每进入一个新块之前，将之前所有数的子集通过二进制枚举$O(d\cdot2^d)$全部预处理出来，之后该块直接$O(1)$完成块间转移，时间复杂度：$O(n\cdot B + \frac{n}{B}\cdot d\cdot 2^d)$。

取B = 1000，可以将运算次数控制在$10^8$级别。

Code_1

#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const int maxx = 2e5 + 10, B = 1000, mod = 1e9 + 7;
int n, d, a[maxx], t[maxx], dp[maxx], ans;
char buf[20];
void add(int &x, int y){
	x += y;
	if(x >= mod) x -= mod;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> d;
	for(int i = 0; i < n; ++i){
		cin >> buf;
		for(int j = 0; j < d; ++j) a[i] = (a[i] << 1) | (buf[j] == '1');
	}
	for(int i = 0; i < n; ++i){
		if(i % B == 0){			//块间转移
			memset(t, 0, sizeof(*t) << d);
			for(int j = 0; j < i; ++j) add(t[a[j]], dp[j]);
			for(int j = 0; j < d; ++j)
				for(int k = 0; k < (1 << d); ++k)
					if((k >> j) & 1) add(t[k], t[k ^ (1 << j)]);
		}
		dp[i] = 1;
		add(dp[i], t[a[i]]);
		for(int j = (i / B) * B; j < i; ++j)	//块内转移
			if((a[j] & a[i]) == a[j])
				add(dp[i], dp[j]);
		add(ans, dp[i]);
	}
	cout << ans << endl;	
	return 0;
}

折半算法

对于这个$d$维二进制，我们可以将其拆成两个部分，将前$\frac{d}{2}$个数视为一个部分，后$\frac{d}{2}$视为一个部分。

$f[i][j]$表示以前半部分为$i$的子集，后半部分为$j$为结尾的序列个数。对于第$i$个数$a[i]$，可以拆成前半部分$x$，与后半部分$y$。

由于$f[i][j]$中包含了前半部分$i$所有子集，所以在统计答案$dp[i]$时可以固定前半部分为$x$，只需要枚举后半部分$y$的子集：

$dp[i] = \sum_{j \in y}f[x][j]$

得到了以第$i$个数的答案后，如何维护$f[i][j]$呢？

这是可以巧妙地发现后半部分$y$是固定的，只需要枚举前半部分$x$的超集：

$f[z][y] += dp[i](x\in z)$

每次统计答案和维护都只需要枚举一半的维度，时间复杂度为$O(n\cdot 2^\frac{d}{2})$。

Code_2

#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const int maxx = 2e5 + 10, B = 1000, mod = 1e9 + 7;
int n, d, f[256][256], ans;
char buf[20];
void add(int &x, int y){
	x += y;
	if(x >= mod) x -= mod;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> d;
	for(int i = 0, a = 0, c = 1; i < n; ++i, a = 0, c = 1){
		cin >> buf;
		for(int j = 0; j < d; ++j) a = (a << 1) | (buf[j] == '1');
		for(int j = (a & 255); j > 0; j = (j - 1) & a)
			add(c, f[a >> 8][j]);
		add(c, f[a >> 8][0]);
		add(ans, c);
		for(int j = a >> 8; j < 256; j = (j + 1) | (a >> 8))
			add(f[j][a & 255], c);
	}
	cout << ans << endl;
	return 0;
}