icontofig | 发布于 2019-10-12 13:42:57 | 阅读量 120 | 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 | 阅读量 335 | 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]
继续阅读