bitset
bitset前身：普通状态压缩的优化
以cf937G为例,对于邻接矩阵的由二维压缩到一维
#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(n^3)\)的本题n是1e3显然无法通过，考虑过程中我们只需要维护01的信息，我们考虑使用bitset的过程将与的过程优化\(O(\frac {n}{w})(w=64)\)
//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学习记录
常用位运算函数
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]\)考虑前i个数，子集和为j的方案，考虑最后需要全部异或起来，偶数方案数直接抵消
因此只需要维护奇偶性，所以我们考虑背包运算中异或，但是现在值域总和2e6,1000个数，显然过不去
考虑bitset优化背包，可达性01用的。由于本题只需要看%2的情况，所以同理也可以使用。时间复杂度：\(O(nm/w)\)
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]\)表示考虑前i个数，和为j的方案数。假设先不取模，我们继续考虑下去。最后统计答案的时候的每次算乘积算的是\(i^{dp[i]}\)。！注意注意注意。dp数组是作为指数出现的，所以我们不能直接对其mod取模。考虑费马小定理，这种指数乘积在mod是质数的时候是以mod-1为周期的，所以我们dp的时候应当对mod-1取模。
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(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)
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/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)\)的时间完成这个处理。
实现：提前开26个bitset预处理每个字母在s的哪些位置出现过。每次遇到一个 t[j]就右移j位对应bitset
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
给你一个字符串 \(s\)，共有 \(q\) 次操作，每个都是下面两种形式的一种。
-
1 i c：将字符串 \(s\) 的第 \(i\) 项变为字符 \(c\)。 -
2 l r y：求字符串 \(y\) 在字符串 \(s\) 中以第 \(l\) 项为起点，以第 \(r\) 项为终点的子串（第 \(l\) 和第 \(r\) 项）中作为子串出现的次数。
\(1\leq |s|\leq 10^5\)，\(1\leq q\leq 10^5\)，\(\sum |y| \leq 10^5\)。
Sol：考虑对于区间查询转化为后缀查询，利用bitset的移位性质，先得到L-n的子串个数，再得到r+1-n的子串个数，做差即可。我们考虑依旧采用上面的思想，维护每个字符的出现位置。利用模式串不断筛选可用的起点，最后为1的位置就是可用的起点。
时间复杂度：\(O(nm/w)\)
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 \pod {|S| \le 10^5}\) ，有 \(n \pod {n \le 10^5}\) 个询问，第 \(i\) 个询问包含一个整数 \(k_i\) 和一个字符串 \(m_i \pod {\sum_i |m_i| \le 10^5}\) 。要求找到一个字符串 \(t\) ，使得 \(t\) 是 \(s\) 的子串并且 \(m_i\) 至少在 \(t\) 中出现了 \(k_i\) 次。你只需要求出 \(t\) 的最短长度。
保证 \(m_i\) 互不相同。
CF963D Frequency of String 题解 - 洛谷专栏 (luogu.com.cn)
Sol：首先考虑对于每个模式串预处理出在远传s中所有可行的endpos，处理手法与上面一样，上面预处理的起点，这里用终点，为了不糊涂改用1_index了，本质一样。我们考虑统计答案的复杂度，直接一想似乎是\(O(nm)\)的无法通过，但注意到题目说每个模式串不同，且总长度不超过1e5,经典根号分治，不同长度的串一定不超过\(\sqrt{\sum{|t_i|}}\)，对于固定长度的串可行endpos的个数是线性的，所以统计答案复杂度是\(O(n\sqrt{n}/w)\)
预处理： 100000*100000/64=1.5e8
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;
}
}