求 $$\sum_{k=1}^{N}((kM)\& M)mod(10^9+7)$$
其中 $1 \le N \le 10^{18}$ , $1 \le M \le 10^{11}$
按位来做，考虑每一个二进制位i, 假设pi是 M 中从小到大第i位上的0/1), 然后我们又可以用取模和取整来取代某一位上的运算，比如当前处理的是第i位 ，就可以写成 $$\sum_{k=1}^{N}(\lfloor \frac{k*M}{2^i} \rfloor)-2*\sum_{k=1}^{N}(\lfloor \frac{k*M}{2^{i+1}} \rfloor)$$
这显然是一个类欧几里得的模板式子，我们只需要套用一下模板即可。最后把所有位的答案累加起来即可。
继续阅读“[类欧几里得][位运算] 2019牛客暑期多校训练营（第九场）I KM and M”
题意：求出给定图的生成子图里有多少个是仙人掌。
首先明确生成子图的概念：包括所有的顶点的子图（之前没有弄明白这个一直没有想出来），那么这个操作其实就很简单了，首先判断图形是否为仙人掌，如果是的话把其中所有的圈（其实在这里就是点双联通分量）所包含的边的数量算出来，Π(cnt[i]+1)即为结果（每个圈最多只能去掉一个边）。
首先，判断是否为仙人掌，这个可以利用无向图仙人掌的性质在dfs求双联通分量的时候顺便求出来：对于任意一个dfs树上的节点u，他的反向边数量+他的子节点中low值小于pre[u]的数量<2，如果大于等于2说明这个节点附近已经产生了两个环了，不可能是仙人掌，反之如果所有点都满足这个要求，那么一定是仙人掌。
其次，求每一个圈的边数。这里如果是仙人掌的话，一定每个点双联通分量都是一个圈（否则就会被判定为非仙人掌，所以这里首先保证第一步的正确性是很重要的），这样的话只需要在求点双联通分量时在退栈的时候把每个bcc对应的边的数量记录下来就可以了（注意是边的数量而不是点的）。
最后套一个无聊的高精度板子就ok了，因为格式错误wa了几次。。。UVALive貌似经常有把格式错误当成wa的。。。顺便这个对高精度的要求还挺高，1000位都满足不了开了100000位才过，至于吗呵呵
思路全在论文里，实现的话费了点功夫。。感觉写这种复杂一点的题，最好还是先把需要用到的变量都写出来，需要的操作都列出来，不然反复修改会浪费很多时间。
需要注意的错误只发现了一个就是在枚举加度的时候可能会出现没边可删的情况（我也不知道为什么），然后这时候我的代码就开始跑环。。因为每次都会新加入一条边，不删边的话必定在树上形成环。后来的策略是一旦当前的操作不再使得生成树变小，那就直接break，因为显然他之后也不会再变小，而且可能之后会出现跑环，而这之前我的代码都是正确的，这样既可以剪枝又可以避免坑。。。 继续阅读“[生成树][treeDP][图论] 最小度限制生成树 POJ1639 Picnic Planning”
