题目大意给出n个k维向量vi，对于k维空间中所有点a，将点a与点a+vi连边，求问全部连接完的图能否完成黑白染色。 题解黑白染色是判断二分图的方法。所以就是要判断所有向量影响后的k维空间中的点是否会形成二分图。 考虑二分图形成的条件：不能出现奇环。 于是问题就转变成了如何判断图中是否会存在奇环。 但是这个题目明显不能用通常的搜索判环解决。 考虑一个点通过这些向量能够通过奇数条边回到自己的等价情况。 假设n个未知数xi，假设一个点想要回到自身，需要使用第i个向量xi次。 于是要形成环即向量方程： x1v1 + x2v2 + ... + xnvn = 0有解。 所以如果要保证形
继续阅读
继续阅读
题目大意给定一个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]
继续阅读
继续阅读