题目大意给定一个n个点的DAG（有向无环图），每个点一开始都是白色，每一次操作会改变一个指定的点的颜色，并询问当前有多少对白点对(u,v)互相可达（存在一条从u到v的有向路径使得路径上全部为白色的点）。 题解可以认为黑色点与其他点都不连通。 所以我们每一次更改点的颜色实际都是再更改图的联通关系。 我们可以通过搜索、topsort、floyd-warshell算法等计算两点间的联通关系（这时候就通过位运算或|来代替Floyd原先的+就好了，因为位运算或即为逻辑加操作）。 但是我们发现这样复杂度是不对的…… 这三种最快的topsort复杂度也是O(qnm)的，明显不符合我们的复杂度要求。 这时候我
继续阅读
继续阅读
题目大意给出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]
继续阅读
继续阅读