Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)
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){
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
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有解。
所以如果要保证形成奇数环的话,就是加入以下一个方程
x1 xor 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
牛客国庆欢乐赛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];
牛客国庆欢乐赛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(