ICPCCamp 2016 Data structure you've never heard of

【题目描述】

给你n个k维0/1向量组成的串a[n]。

定义向量a <= b当且仅当a中每一个1出现的位置在b中都是1

比如{0,1,0,1}<={0,1,0,1}, {0,1,0,1}<={0,1,1,1}

但是{0,1,0,1}和{1,0,0,1}没有这样的关系

现在请你统计这个串中有多少个不下降子序列。

一个子序列是一个1~n组成的序列，

其中每个元素都满足i < j且a[i] <= a[j]。

【输入】

第一行两个正整数n，k。n表示串的长度，k表示向量维数

下面n行每一行一个0/1字符串表示一个k维向量

【输出】

输出一个整数，表示不下降序列个数。

【输入样例】

2 2
01
11

【输出样例】

【提示】

对于30%的数据， $n \leq 5000$

对于100%的数据， $n \leq 100000, k \leq 16$

$n \leq 100000, k \leq 16$ $n \leq 100000, k \leq 16$ $n \leq 100000, k \leq 16$

考虑这个结构，我们修改是O(2^8)枚举后8位，查询是O(2^8)枚举前8位。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
#define SubSet(i, a) for(register int i = a; i; i = (i - 1) & a)
#define SuperSet(i, a) for(register int i = a; i < ST; i = (i + 1) | a)
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int B = 8, ST = 1 << B;
int dp[maxn], n, ans;
int DS[ST + 5][ST + 5], lowmask, topmask;
int a[maxn], b, tmp;
char s[25];

void AddMod(int &x, int y) {
	x += y;
	if(x >= mod) x -= mod;
}

void add(int x, int w) {
	tmp = (x & topmask) >> B;
	SuperSet(i, (x & lowmask)) AddMod(DS[tmp][i], w);	
}

int query(int x) {
	int ans = 0;
	tmp = (x & lowmask);
	SubSet(i, (x & topmask) >> B) 
		AddMod(ans, DS[i][tmp]);
	AddMod(ans, DS[0][tmp]);
	return ans;
}

int main() {
	scanf("%d%d", &n, &b);
	lowmask = ST - 1;
	topmask = (ST - 1) << B;
	For(i, 1, n) {
		scanf("%s", s);
		For(j, 0, b - 1) 
			a[i] = a[i] * 2 + (s[j] == '1');
	}
	ans = dp[1] = 1, add(a[1], 1);
	For(i, 2, n) {
		dp[i] = query(a[i]) + 1;
		add(a[i], dp[i]);
		AddMod(ans, dp[i]);
	}
	printf("%d", ans);
	return 0;
}

Rockdu's Blog