icontofig | 发布于 2020-04-16 21:31:39 | 阅读量 548 | 高斯消元 bitset
发布于 2020-04-16 21:31:39 | 高斯消元 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有解。 所以如果要保证形
继续阅读
icontofig | 发布于 2019-10-12 13:42:57 | 阅读量 143 | bitset topsort
发布于 2019-10-12 13:42:57 | bitset topsort
牛客国庆欢乐赛5 2017四川省赛 D.Dynamic Graph  bitset加速 + topsort
题目大意给定一个n个点的DAG(有向无环图),每个点一开始都是白色,每一次操作会改变一个指定的点的颜色,并询问当前有多少对白点对(u,v)互相可达(存在一条从u到v的有向路径使得路径上全部为白色的点)。 题解可以认为黑色点与其他点都不连通。 所以我们每一次更改点的颜色实际都是再更改图的联通关系。 我们可以通过搜索、topsort、floyd-warshell算法等计算两点间的联通关系(这时候就通过位运算或|来代替Floyd原先的+就好了,因为位运算或即为逻辑加操作)。 但是我们发现这样复杂度是不对的…… 这三种最快的topsort复杂度也是O(qnm)的,明显不符合我们的复杂度要求。 这时候我
继续阅读
icontofig | 发布于 2019-10-05 21:34:07 | 阅读量 382 | DP bitset 数论
发布于 2019-10-05 21:34:07 | 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]
继续阅读