Tag-bitset

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2021-01-15 19:36:41 |  0 Comments  |  bitset 高斯消元

2020ICPC 济南site A Matrix Equation bitset + 异或高斯消元

题目大意

求矩阵C的个数,满足A×C = B·C。其中×表示矩阵乘(模数为2,也即矩阵的异或乘),·表示矩阵元素与。

题解

博主在正式赛的时候执着于找规律,最后才看到高斯消元,所以最后就白给了,拿了个铜滚粗了。

其实没必要去算什么规律的,我们直接设C的元素为c11 ……cnn,然后直接按照两种操作的定义展开即可。

之后我们可以发现c中的元素的每一列都构成了一组n元的异或方程组,而不同列之间的元素是没有相互影响的。这样我们就可以应用高斯消元,求解自由元的个数,计算出每一列自由元个数xi,最后结果就是Πxi。算法的总复杂度是O(n4)的

但是这个题目的数据是N ≤ 200,所以算法O(n4)的时间复杂度是无法接受的,但是我们又无法做到在指数级上进行优化,所以考虑常数优化。考虑到异或方程组的行间计算实际上都是异或操作,所以我们可以考虑用bitset代替自己写的数组式矩阵。这样最终算法的时间复杂度为O(n4/64)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll quick_pow(ll x,ll y){
	ll res = 1;
	while(y){
		if(y & 1)
			res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
const int maxn = 205;
int a[maxn][maxn],b[maxn][maxn];
bitset<maxn>bs[maxn],bd[maxn],t;
int n;
ll ans;
void swap(bitset<maxn> &x,bitset<maxn> &y){
	t.reset();
	t |= y;
	y.reset();
	y |= x;
	x.reset();
	x |= t;
	return;
}
int Guass(){
	int maxrow,row = 0,col = 0,num = 0;
	for(row = 0;row < n && col < n;row++,col++){
		maxrow = row;
		for(int i = row + 1;i < n;++i){
 2020-09-16 20:28:10 |  0 Comments  |  bitset

Nowcoder Muti-School Training 2 G Greater and Greater bitset加速

题目大意

给出一个长为n的数列A,一个长为m的数列B

求问A中有多少个长度为m的子区间S,满足S中的元素全都不小于B中下标对应的元素

题解

说实话真的还是对bitset的应用不熟悉。

这题bitset只是最后用来优化的。

首先我们假定一个tmp数组,其中tmp[i][j]表示对Ai是否≥Bj。

如果一个长度为m的子区间要成为满足题目条件的S,那么和tmp[i]数组有什么关系?

一定是要求:对于区间内每一个i及其对应位置的j,tmp[i][j]都为1.这是显然的。

考虑如何优化这个问题。

首先,大小关系其实本质上来说只有m+1种,也就是对于tmp[i]的取值最多有m+1种,所以我们可以将B数组内的数全部排序,然后用m+1个bitset(假设为s)逐位去置1,然后九不需要算tmp数组了,我们需要取用tmp的时候,只需要找到最后一个小于等于A[i]的B[j](这里的B已经排序好了),然后取s[j]就可以了。而且bitset也会在我们接下来的做法中发挥很重要的作用。预处理这些bitset的复杂度是O(m2/W)的(W为bitset优化的效果)

之后考虑如何去搞这个题。

新设一个新的m位bitset,假设为curi,其中curi[j] = 1当且仅当对于所有的k∈[j,m],Ai+k-j >= Bk,这样只需要求有多少curi[1] = 1即可。

首先可以确定A数组的后m-1个数是肯定不可以作为区间点的,毕竟区间长度都不够,所以我们可以按照下面的公式来做:

curi = ((curi+1 >> 1) | Im) & sposi。posi表示最后一个小于等于A[i]的B[posi]。

这样通过右移位来进行对齐,可以达到我们预期的效果。

而且,我们可以不用开n个cur,只需要开一个进行滚动就可以了。

最终的时间复杂度是O(nm/W)

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PI;
const int maxn = 150005;
const int maxm = 40005;
PI a[maxn],b[maxm];
bitset<maxm>s[maxm];
bitset<maxm>cur,upd;
const int INF = 1e9+7;
int n,m;
int p;
int main(){
    ios_ba
 2020-04-16 21:31:39 |  0 Comments  |  高斯消元 bitset

2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest I . Infinite Gift

题目大意

给出n个k维向量vi,对于k维空间中所有点a,将点a与点a+vi连边,求问全部连接完的图能否完成黑白染色。

题解

黑白染色是判断二分图的方法。所以就是要判断所有向量影响后的k维空间中的点是否会形成二分图。

考虑二分图形成的条件:不能出现奇环。

于是问题就转变成了如何判断图中是否会存在奇环。

但是这个题目明显不能用通常的搜索判环解决。

考虑一个点通过这些向量能够通过奇数条边回到自己的等价情况。

假设n个未知数xi,假设一个点想要回到自身,需要使用第i个向量xi次。

于是要形成环即向量方程:

x1v1 + x2v2 + ... + xnvn = 0有解。

所以如果要保证形成奇数环的话,就是加入以下一个方程

xxor x2 xor ... xor xn = 1

联立来解一个n元k+1维方程组。

将上面的向量方程拆分到k维k个方程,并将所有运算全都mod 2处理,即可让整个方程组变成一个异或方程组。

能形成二分图的条件就是方程组不存在解,否则就说明构成的图不是二分图。

使用高斯消元解决方程组判断解的问题。

但是高斯消元有一个问题,就是复杂度不对,为O(nk2)

不过由于这道题的方程组的运算只与二进制异或有关,所以可以把方程的参数放入bitset加速,最终复杂度为O(nk2/64)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1505;
bitset<maxn>g[maxn];
int n,k,now,x;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= k;++j){
            cin >> x;
            g[j][i] = abs(x) % 2;
        }
    }
    for(int i = 1;i <= n+1;++i){
        g[k+1][i] = 1;
    }
    now = 0;
    for(int i = 1;i <= n;++i){
        int j
 2019-10-12 13:42:57 |  0 Comments  |  bitset topsort

牛客国庆欢乐赛5 2017四川省赛 D.Dynamic Graph bitset加速 + topsort


题目大意

给定一个n个点的DAG(有向无环图),每个点一开始都是白色,每一次操作会改变一个指定的点的颜色,并询问当前有多少对白点对(u,v)互相可达(存在一条从u到v的有向路径使得路径上全部为白色的点)。

题解

可以认为黑色点与其他点都不连通。

所以我们每一次更改点的颜色实际都是再更改图的联通关系。

我们可以通过搜索、topsort、floyd-warshell算法等计算两点间的联通关系(这时候就通过位运算或|来代替Floyd原先的+就好了,因为位运算或即为逻辑加操作)。

但是我们发现这样复杂度是不对的……

这三种最快的topsort复杂度也是O(qnm)的,明显不符合我们的复杂度要求。

这时候我们注意到对于联通关系,两点间的联通关系也即用0表示不连通,1表示联通。

我们对于更新也是这样的:

假设当前检索点为u,下一个点为v,则对于所有联通u的点k,假设mp[i][j]表示是否可从i联通到j,则有

mp[k][v] = mp[k][u]; ----> mp[k][v] |= mp[k][u];

可以看到这个更新过程实际上只有位运算的或操作,只有0和1的运算,所以可以用bitset进行加速。

当我们检索到当前的点u时,先预处理设定mp[u][u] = 1,表示当前点可以到达当前点。最终因为答案是算不相同的点u和v联通个数,所以最后进行统计的时候答案整体-n即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
int d[maxn],tmp[maxn];
bitset<305>con[maxn];
queue<int>qk;
vector<int>g[maxn];
int n,m,q;
int a,b;
int c[maxn],vis[maxn];
void topsort(){
    for(int i = 1;i <= n;++i)
        con[i].reset();
    for(int i = 1;i <= n;++i){
        if(!c[i])
            con[i][i] = 1;
        vis[i] = 0;
    }
    for(int i = 1;i <= n;++i){
        tmp[i] = d[i];
      
 2019-10-05 21:34:07 |  0 Comments  |  DP bitset 数论

牛客国庆欢乐赛5 2017四川省赛 K-2017Revenge bitset加速dp、原根

题目大意

给出n个数,要你从中选出一些数,使得他们的乘积mod 2017的余数为r,问总方案数mod 2的值。

题解

对于一些数的乘法,我们可以用log把他转化乘加法。

但是是在模意义下,就是需要离散模对数了。

这时候我们要求2017的原根,2017的原根是5,我们就可以自然而然的把原来的所有数都化为他们的离散模对数了。

首先如果数据范围很小,我们该怎么写呢?

那么我们可以用dp[i][j]表示当前为第枚举到第i个数,选出的前面的(包括i)所有数的乘积的离散模对数为j的方案数。

那么dp方程就很容易能够想到了:

dp[i][j] = dp[i-1][j] + (dp[i-1][(j-lg[a[i]])%2016]);

这两项分别代表当前项选/不选的情况。

可以看到第i位的值只跟他的前一位有关,所以空间可以滚动掉一维。

但是这样的时间仍然是O(n*2016),n的数据范围让我们无法直接这样去做dp(而且由于依赖性无法使用多线程,这里我又在说胡话了)。

那我们该怎么办?

我们注意一下,答案只需要输出总方案数mod 2的值,所以注意一下dp方程,我们就可以这样去改了:

dp[i][j] = dp[i-1][j] ^ (dp[i-1][(j-lg[a[i]])%2016]);(二进制中的异或运算实际上就是加法对2取模)

也就是dp[j] = dp[j] ^ dp[(j-lg[a[i]])%2016];

计算机系统在进行二进制运算的时候是非常快的,所以可以用二进制的一些东西来加速这个运算,让枚举2016次的复杂度降低成为一个更小的常数,但是通常的数据类型不支持我们这么做。

这时候我们可以用C++中的bitset来对上面的式子进行加速。

如果我们用一个2016位的bitset<2016>f,那么上面的递推式就要写成以下形式:

f ^= (f<<lg[a[i]]) ^ (f>>(2016-lg[a[i]]));

这样由于计算机系统在对于bitset运算的速度较快,我们就可以通过此题了。

注意一定要用cout输出,printf输出会有问题。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
int lg[2020],a[2000005],n,r;
bitset<2016>f;
int main(
Title - Artist
0:00