bitset

bitset前身：普通状态压缩的优化

以cf937G为例,对于邻接矩阵的由二维压缩到一维

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
#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<std::string> g(n), w(n);
    for (int i = 0; i < n; i++) {
        std::cin >> g[i] >> w[i];
    }
    
    std::vector<int> e(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i] == g[j] || w[i] == w[j]) {
                e[i] |= 1 << j;
            }
        }
    }
    
    std::vector<int> dp(1 << n);
    for (int x = 0; x < n; x++) {
        dp[1 << x] |= 1 << x;
    }
    
    int ans = 0;
    for (int s = 1; s < (1 << n); s++) {
        if (dp[s]) {
            ans = std::max(ans, __builtin_popcount(s));
        }
        for (int y = 0; y < n; y++) {
            if ((~s >> y & 1) && (dp[s] & e[y])) {
                dp[s | 1 << y] |= 1 << y;
            }
        }
    }
    std::cout << n - ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

floyd求可达性传递闭包

Solution:初步做法：首先本题只需要求所有偏序关系，考虑建图的时候只建单向图。朴素floyd是O(n3)O(n^3)的本题n是1e3显然无法通过，考虑过程中我们只需要维护01的信息，我们考虑使用bitset的过程将与的过程优化O(nw)(w=64)O(\frac {n}{w})(w=64)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//floyd计算，优化64常数判断，bitset优化可达性邻接矩阵
//需要保证任意两点相互可达，
bitset<N>dp[N];
void solve(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		dp[u][v]=1;
	}
	//注意枚举顺序，先枚举中转点i
	for(int k=1;k<=n;k++){
		//枚举起点
		for(int i=1;i<=n;i++){
			//k能到的，i也能到
			if(dp[i][k])dp[i]|=dp[k];
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)ans+=dp[i].count();
	ans=n*(n-1)/2-ans;
	cout<<ans<<endl;
}

听dmy学习记录

常用位运算函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ll n=(1LL<<40)-1LL;
	cout<<__builtin_popcountll(n)<<endl;//二进制里1的个数
	//40
	cout<<__lg(n)<<endl;//等价于 31-__builtin_clz(n);
	//39
	
	
	
	cout<<63-__builtin_clzll(n)<<endl;//最高位开始连续0的个数
	//39
	
	cout<<__builtin_ctz(8)<<endl;//最低位开始连续0的个数
	//3
	
	bitset<5>B=21;
	cout<<B<<endl;
for(int i = (int)(B._Find_first()); i != B.size();i = (int)(B._Find_next(i)))
    cout << i << " ";
    //找到所有含1的位置
    
   // 10101
//    0 2 4

bzoj3687https://hydro.ac/d/bzoj/p/3687

题意：求所有子集和的异或和

Solution：首先我们不可能枚举所有子集，所以我们只能考虑dp。dp[i][j]dp[i][j]考虑前i个数，子集和为j的方案，考虑最后需要全部异或起来，偶数方案数直接抵消

因此只需要维护奇偶性，所以我们考虑背包运算中异或，但是现在值域总和2e6,1000个数，显然过不去

考虑bitset优化背包，可达性01用的。由于本题只需要看%2的情况，所以同理也可以使用。时间复杂度：O(nm/w)O(nm/w)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bitset<M>b;
void solve(){
	cin>>n;
	b[0]=1;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		b^=(b<<x);
		//cerr<<b<<endl;
	}
	ll ans=0;
	for(int i=1;i<=1000000;i++){
		if(b[i])ans^=i;
	}
	cout<<ans<<endl;
}

SDUT2023校赛https://acm.sdut.edu.cn/onlinejudge3/contests/4098/problems/O

题意：给定一个集合1-n。求所有子集和的乘积.(n<=200)

Solution：考虑值域和数据个数，可以直接dp。dp[i][j]dp[i][j]表示考虑前i个数，和为j的方案数。假设先不取模，我们继续考虑下去。最后统计答案的时候的每次算乘积算的是idp[i]i^{dp[i]}。！注意注意注意。dp数组是作为指数出现的，所以我们不能直接对其mod取模。考虑费马小定理，这种指数乘积在mod是质数的时候是以mod-1为周期的，所以我们dp的时候应当对mod-1取模。

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
int dp[N*N];[j]
int qmi(int a,int b){
	//cerr<<a<<" "<<b<<" ";
	int res=1LL;
	while(b){
		if(b&1)res=(res*a)%mod;
		a=a*a%mod;
		b>>=1;
	}
	//cerr<<res<<endl;
	return res;
	
}
//相当于对cnt次数取模了，这是对指数取模，是不合法的、
//考虑费马小定理每p-1个数为1
void solve(){
	cin>>n;
	dp[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=n*(n+1)/2;j>=i;j--){
			dp[j]+=dp[j-i];dp[j]%=(mod-1);
		}
	}
	int ans=1LL;
	for(int i=1;i<=n*(n+1)/2;i++)
	{
		int cnt=dp[i];
		//cerr<<i<<" "<<dp[i]<<endl;
		ans*=qmi(i,cnt);ans%=mod;
	}
	cout<<ans<<endl;
}

DAG计数：O(n2/w)O(n^{2}/w)的解法

题意：有向无环图，输入都是小向大连边，求出每个点能到达多少点？

Solution：考虑如果u到v有边，那么v所能到达的点u也能到达，直接利用bitset的或运算就可以完成。f[u]|=f[v]

检查时间：50000*50000/64=4e7

计算空间：50000*50000/8/1024/1024=298MB(bit->byte->kb->MB)

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
bitset<N>f[N];
vector<int>e[N];
/*debug
5 0000100000 
4 0000010000 
3 0000101000 
2 0000101100 
1 0000111110 

input
5 5
1 2
1 4
2 3
2 5
3 5

out
5
3
2
1
1
*/
void solve(){
	cin>>n;cin>>m;
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		e[u].push_back(v);
	}
	//逆序就是拓扑序
	for(int i=n;i>=1;i--){
		f[i][i]=1;
		for(auto v:e[i]){f[i]|=f[v];}
		cerr<<i<<" "<<f[i]<<endl;
	}
	for(int i=1;i<=n;i++)cout<<f[i].count()<<endl;
}

bitset还可以解决解决三元环计数，求传递闭包。思路都是枚举两个点，将枚举第三点的耗时从O(n)O(n)优化成O(n/w)O(n/w)。

三元环计数详情见该专题

bitset解决动态带修字符串匹配

https://hydro.ac/d/bzoj/p/4503 带通配符的字符串匹配

题意：给长串s，模式串t，t中含有？作为通配符，求s中t出现了几次，分别在哪开始？

Sol：考虑有通配符不好用kmp做，有FFT做法，待补。利用bitset的思想是维护s中每个位置作为起点是否可行。对于t中字母 t[j]，对于s中所有不为这个字母的位置i，则i-j一定无法作为起点，我们利用bitset可以对于每个j花费O(n/w)O(n/w)的时间完成这个处理。

实现：提前开26个bitset预处理每个字母在s的哪些位置出现过。每次遇到一个 t[j]就右移j位对应bitset

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bitset<N>b[28];
bitset<N>ans;
void solve(){
	string s,t;cin>>s>>t;
	n=s.size();m=t.size();
	for(int i=0;i+m-1<n;i++)ans[i]=1;
	for(int i=0;i<n;i++)b[s[i]-'a'][i]=1;
	for(int i=0;i<m;i++){
		if(t[i]=='?')continue;
		ans&=b[t[i]-'a']>>i;
	}
	cout<<ans.count()<<endl;
	for(int i=0;i+m-1<n;i++){
		if(ans[i]==1)cout<<i<<endl;
	}
}

多次区间查询给出原串，模式串保持不变，且动态带修。http://codeforces.com/problemset/problem/914/F

给你一个字符串 ss，共有 qq 次操作，每个都是下面两种形式的一种。

  • 1 i c：将字符串 ss 的第 ii 项变为字符 cc。

  • 2 l r y：求字符串 yy 在字符串 ss 中以第 ll 项为起点，以第 rr 项为终点的子串（第 ll 和第 rr 项）中作为子串出现的次数。

1≤∣s∣≤1051\leq |s|\leq 10^5，1≤q≤1051\leq q\leq 10^5，∑∣y∣≤105\sum |y| \leq 10^5。

Sol：考虑对于区间查询转化为后缀查询，利用bitset的移位性质，先得到L-n的子串个数，再得到r+1-n的子串个数，做差即可。我们考虑依旧采用上面的思想，维护每个字符的出现位置。利用模式串不断筛选可用的起点，最后为1的位置就是可用的起点。

时间复杂度：O(nm/w)O(nm/w)

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
bitset<N>b[28];
bitset<N>ans;
void solve(){
	string s;cin>>s;
	int len=s.size();
	for(int i=0;i<len;i++)b[s[i]-'a'][i]=1;
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int op;cin>>op;
		if(op==1){
			int pos;cin>>pos;pos--;
			char c;cin>>c;
			b[s[pos]-'a'][pos]=0;
			s[pos]=c;
			b[s[pos]-'a'][pos]=1;
		}
		else {
			int l,r;cin>>l>>r;l--;r--;
			ans.set();
			string t;cin>>t;n=t.size();
			if(r-l+1<n){
				cout<<0<<endl;
				continue;
			}
			for(int i=0;i<n;i++){
				ans&=b[t[i]-'a']>>i;		
			}
			int cl=(ans>>l).count(),cr=(ans>>(r+2-n)).count();
			cout<<cl-cr<<endl;
			
		}
	}
}

根号分治bitset+滑动窗口http://codeforces.com/problemset/problem/963/D

给你一个字符串 s(∣S∣≤105)s \pod {|S| \le 10^5} ，有 n(n≤105)n \pod {n \le 10^5} 个询问，第 ii 个询问包含一个整数 kik_i 和一个字符串 mi(∑i∣mi∣≤105)m_i \pod {\sum_i |m_i| \le 10^5} 。要求找到一个字符串 tt ，使得 tt 是 ss 的子串并且 mim_i 至少在 tt 中出现了 kik_i 次。你只需要求出 tt 的最短长度。
保证 mim_i 互不相同。

CF963D Frequency of String 题解 - 洛谷专栏 (luogu.com.cn)

Sol：首先考虑对于每个模式串预处理出在远传s中所有可行的endpos，处理手法与上面一样，上面预处理的起点，这里用终点，为了不糊涂改用1_index了，本质一样。我们考虑统计答案的复杂度，直接一想似乎是O(nm)O(nm)的无法通过，但注意到题目说每个模式串不同，且总长度不超过1e5,经典根号分治，不同长度的串一定不超过∑∣ti∣\sqrt{\sum{|t_i|}}，对于固定长度的串可行endpos的个数是线性的，所以统计答案复杂度是O(nn/w)O(n\sqrt{n}/w)

预处理： 100000*100000/64=1.5e8

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
bitset<N>b[28];
bitset<N>ans;
void solve(){
	cin>>s;n=s.size();
	s=" "+s;
	for(int i=1;i<=n;i++)b[s[i]-'a'][i]=1;
	int q;cin>>q;
	for(int i=1;i<=q;i++){
		int k;cin>>k;
		ans.set();
		vector<int>v;
		string t;cin>>t;
		m=t.size();t=" "+t;
		for(int i=1;i<=m;i++){
			ans&=b[t[i]-'a']<<(m-i);
			//左移m-1位的时候。ans前面的不合法低位就变为0了
            //左移1的时候，ans高位不合法的就没了
		}
for(int pos=ans._Find_first();pos!=N;pos=ans._Find_next(pos)) v.push_back(pos);
int res=inf;
for(int i=k-1;i<v.size();i++){
	
	//l=r1-m+1
	//r=r2
	//len=r-l+1=r2-r1+m
	res=min(res,m+v[i]-v[i-k+1]);
}
if(res==inf)cout<<-1<<endl;
else cout<<res<<endl;
	}
}

总结：对于以上字符串匹配需要注意的细节：下标移动和边界的计算（可以设未知数）。不合法情况导致越界需要提前特判退出。最后一题那个找1的上界没想清楚

bitset配合莫队在数据结构方面的应用