Tag-bitset

题目大意

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

题解

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

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

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

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

题目大意

给出一个长为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(m²/W)的（W为bitset优化的效果）

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

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

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

cur_i = ((cur_i+1 >> 1) | I_m) & s_posi。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

题目大意

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

题解

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

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

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

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

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

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

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

x₁v₁ + x₂v₂ + ... + x_nv_n = 0有解。

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

x₁ xor x₂ xor ... xor x_n = 1

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

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

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

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

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

不过由于这道题的方程组的运算只与二进制异或有关，所以可以把方程的参数放入bitset加速，最终复杂度为O(nk²/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

题目大意

给定一个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];
      

题目大意

给出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(