【题目描述】：
    浩浩荡荡的cg大军发现了一座矿产资源极其丰富的城市，他们打算在这座城市实施新的采矿战略。
　　这个城市可以看成一棵有n个节点的有根树，我们把每个节点用1到n的整数编号。为了方便起见，对于任何一个非根节点v，它任何一个祖先的编号都严格小于v。树上的每个节点表示一个矿点，每条边表示一条街道。
　　作为cg大军的一个小队长，你拥有m个部下。你有一张二维的动态信息表，用Ti,j表示第i行第j列的数据。当你被允许开采某个区域时，你可以将你的部下分配至各个矿点。在第i个矿点安排j个人可以获得Ti,j单位的矿产。
　　允许开采的区域是这样描述的：给你一对矿点(u,v)，保证v是u的祖先（这里定义祖先包括u本身）；u为你控制的区域，可以在以u为根的子树上任意分配部下；u到v的简单路径（不包括u但包括v，若u=v则包括u）为探险路径，在该路径上你可以选择至多一个矿点安排部下。你这次开采的收益为安排有部下的矿点的收益之和。
【题目解法】：
    不建议在bzoj上看题目，排版简直...TAT

http://www.tsinsen.com/ViewGProblem.page?gpid=A1219

    按照dfs序进行树链剖分，这样既可以维护子树信息，又可以维护链上信息
    令f[i]表示设置任意数量的矿点时放置i个人的最大价值
    令g[i]表示设置一个矿点是放置i个人的最大价值
    将f,g放在线段树每一个结点中
    合并的时候：
    对于f：now.f[i]=max(lc.f[j]+rc.f[i-j])
    对于g：now.g[i]=max(lc.g[i],rc.g[i])
    修改的复杂度为O(C*m^2 log n)
    查询的复杂度为O(C*m log^2 n+C*m)

阅读更多……

【题目描述】：
    无线网络基站在理想状况下有效信号覆盖范围是个圆形。而无线基站的功耗与圆的半径的平方成正比。
现给出平面上若干网络用户的位置,请你选择一个合适的位置建设无线基站....
就在你拿起键盘准备开始敲代码的时候,你的好朋友发明家 SHTSC 突然出现了。SHTSC 刚刚完成了他的新发明——无线信号增幅仪。增幅仪能够在不增加无线基站功耗的前提下,使得有效信号的覆盖范围在某一特定方向上伸长若干倍。即:使用了增幅仪的无线基站覆盖范围是个椭圆,其功耗正比于半短轴长的平方。现给出平面上若干网络用户的位置,请你选择一个合适的位置建设无线基站,并在增幅仪的帮助下使所有的用户都能接收到信号,且无线基站的功耗最小。
    注意:由于SHTSC 增幅仪的工作原理依赖地磁场,增幅的方向是恒定的。
【题目解法】：
    显然最小椭圆覆盖是很难实现的
    我们可以把点顺时针旋转a度，然后x坐标缩短为1/p，就可以把覆盖变成圆形了
    然后就是最小圆覆盖了，模拟退火估计也是可以的
    复杂度O(N)

阅读更多……

【题目描述】：

【题目解法】：
    炖了狗了！我他妈真是SB的可以啊，居然写了LCT TAT
    我们可以把这道题看成动态加边，动态删边，维护联通块个数的SB模板题
    由于不强制在线，我们维护删除时间的最大生成树，然后就可以实现动态图的问题了
    然后6k+的代码就出来了，他妈让我怎么调啊！
    写了一晚，调了一下午，最后下了数据发现：
    1
    1
    10
    1 1
    1 1
    1 1
    1 1
    1 1
    1 1
    1 1
    1 1
    1 1
    1 1
    卧槽？还有这样的棋盘，日狗！
    然后特判一下就过了，不过跑的飞快！

阅读更多……

【题目描述】：
    当被传到球之后，不同的人会做出不同的动作。
    第1类人，顺着传来的方向传给下一个人。
    第2类人，逆着传来的方向传给上一个人。
    第3类人，顺着传来的方向传给下面第二个人。
    第4类人，逆着传来的方向传给上面第二个人。
    现不知是从哪个人开始传，及开始传的方向，求有哪些人无论如何，最多只能碰到一次球（开始传球的人算碰到了一次球）。（第3、4类人发球也是越过和自己相邻的人传给第二个人）。
【题目解法】：
    《看错题目系列》 真是炖了狗了
    注意题目里面说的最多只能碰到一次球值得是再一次传球游戏中，而不是在所有的传球游戏中TAT
    然后就好了嘛...
    我们先对每个人拆点，表示顺时针接的和逆时针接的，我们成他们为对立点
    然后按照题目要求连边，然后跑tarjan
    一个点是答案当且仅当：
    1.他所在的强联通分量中只有他一个点
    2.他与它的对立点不在缩点后DAG的一条路径上
    对于1很好判断，对于2我们只要dfs遍历是进入某个点将他的标记置为true，离开时置为false，然后判断对立点是否标记为true即可
    复杂度O(N)

阅读更多……

【题目描述】：
    很久很久以前，森林里住着一群跳蚤。一天，跳蚤国王得到了一个神秘的字符串，它想进行研究。
    首先，他会把串分成不超过 k 个子串，然后对于每个子串 S，他会从S的所有子串中选择字典序最大的那一个，并在选出来的 k 个子串中选择字典序最大的那一个。他称其为“魔力串”。
    现在他想找一个最优的分法让“魔力串”字典序最小。
【题目解法】：
    显然答案具有单调性，且答案一定是原串的一个子串
    因此我们二分K，验证第K小子串是否满足要求
    首先我么求出原串的后缀数组，然后可以在O(N)时间内找到K小子串，设为[L,R]
    然后我们贪心的从后往前一个一个字符加入，假设现在已经分段到j，那么我们i=j i--，知道找到某个子串[i,j]满足[L,R]<[i,j]，那么此时我们必须在i和i+1直接分开，因此此时我们把需要分开的次数+1，然后j=i，继续向前找，可以证明这样划分的方案是最优的
    我们只要判断最后需要划分的次数是否小于等于给出的k即可
    当然如果对于某个单个字符[i,i]满足[L,R]<[i,i]显然这个字符串是不满足的，因为我们无法把[i,i]分割开来
    时间复杂度O(N log N)

阅读更多……

【题目描述】：

【题目解法】：
    枚举d=gcd(i,j)
    ans=sigma(d^d*sigma(i^d)*sigma(j^d)*sigma(mu(k))) 1<=i<=n/d  1<=j<=m/d  k|i且k|j
    ans=sigma(d^d*sigma(mu(k)*sigma(i^d)*sigma(j^d)*k^d*k^d))  1<=k<=n/d  1<=i<=n/kd  1<=j<=m/kd1
    然后我们O(N)枚举d，然后O(N/d)枚举k并且计算sigma(i^d)，然后就可以O(1)的到后面的答案
    合并即可，复杂度O(N log N)

阅读更多……

【题目描述】：
    在XYZ的dzy loves math6问世后，dzy一直觉得这道题答案太大，一点都不优美，于是他随手在外面套上一个μ。同时，他又觉得输入两个数实在太麻烦，于是题目变成了：

    你能解决这个问题吗？
【题目解法】：
    首先我们知道只有不含有平方因子的数mu才不为0
    因此gcd(i,j)=1（不会html别打我TAT...）
    所有ans=sigma(mu(ij)*sigma(mu[d]){d|i d|j})=sigma(mu(i)*sigma(mu(d)*g(i,d){d|i}))
    其中g(i,d)=sigma(mu(d)+mu(2d)+...+mu(n))
    因此我们可以枚举i，然后计算此时的答案与ans[i-1]累加即为ans[i]
    首先我们知道mu(i)!=0，因此i不含有平方因子，然后把i分解质因数最多只有log级别个大概是20+
    因此我们可以暴力枚举i的因子，然后计算g
    我们知道g(i-d,d)的答案已经知道，g(i,d)=g(i-d,d)+mu(i)
    因此每次更新g即可，然后根据上面的式子计算即可
    然而我发现分解质因数的方法太慢了！！！
    然后去%claris的程序，发现我们可以预处理出minnum[i]表示i的最小质因子
    然后就可以在log的时间下求出所有的质因子，而且速度很快！%%%claris

阅读更多……

【写在前面】：
    其实很早之前就已经知道这个东西了
    最近做了一道BSGS的题目，有感而发
    决定扯一下淡，顺便加深一下记忆
    为啥要把BSGS和逆元一起讲呢？因为BSGS里面也牵涉到了逆元的相关知识（虽然并没有什么关系）
【参考】：

http://www.cnblogs.com/yuiffy/p/3877381.html

http://blog.csdn.net/wyfcyx_forever/article/details/40538515

http://hi.baidu.com/aekdycoin/item/236937318413c680c2cf29d4 （写的很好不过hi.baidu已经SB了TAT）

http://quartergeek.com/bsgs/

http://www.cnblogs.com/mengfanrong/p/4660834.html

http://blog.miskcoo.com/2014/09/linear-find-all-invert （这个是线性求逆元的）

【线性求逆元】：
    我们称 A^(-1) mod p为A在mod p意义下的逆元
    显然在p为质数且(A,p)=1时可以用欧拉定理搞定
    然A p没有任何联系时，我们可以用扩展欧几里德求出，这样求解[1,n]的逆元复杂度为O(n log n)
    我们考虑一个SB的事实p mod p=0
    然后我们令p=k*i+r (1<=i<p r<i)
    显然k*i+r mod p=0
    两边同乘i^(-1)*r^(-1)得到 k*r^(-1)+i^(-1) mod p=0
    i^(-1) mod p=-k*r^(-1)
    显然k=p/i，r=p%i代入原式可以得到i^(-1) mod p=-p/i*(p%i)^(-1)
    因此我们令rev[i]表示i的逆元，那么rev[i]=-(p/i)*rev[p%i]
    递推处理即可，复杂度O(N)
    同时这篇blog还提供了O(log p)复杂度求出单个逆元
    p%i<=p/2，然后就可以递归处理了
【简介】：
    首先BSGS的全称是：Baby Step Giant Step
    它主要用来求解这样的问题：A^x mod p=B的最小非负整数解
    BSGS分为质数版和extend版，我们分开总结一下
【质数版BSGS】：
    所谓质数版指的是p为指数的情况
    我们考虑p为指数时，根据费马小定理可以知道 0<=x<p
    显然暴力枚举的复杂度是O(p)的，当p较大时显然不适用
    我们可以这样考虑：令x=C*i+j（其中C为常数）
    代入原式可得(A^C)^i*A^j mod p=B
    显然我们可以用0<=i<=p/C
    于是我们可以用O(C)的时间求出A^C 然后再用O(p/C)的时间枚举i
    于是问题就转化为是否存在一个j满足D*A^j mod p=B，D为确定的值
    A^j mod p=B/D，其中0<=j<C
    我们可以用O(C)的时间预处理出A^j mod p的值，存入map里面
    然后可以在log的时间复杂度内查询最小的j满足条件
    显然我们取C=sqrt(p)，那么整个算法的复杂度就是O(sqrt(p) log sqrt(p))
    B/D可以利用扩展欧几里德或者欧拉定理算出来
【extend版BSGS】
    如果p不是质数，那么可能会出现gcd(A,p)!=1的时候
    我们考虑在求解D*A^j mod p=B时候如果gcd(D,p)!=1时的情况
    由于D=A^C，因此就是gcd(A,p)!=1的情况，此时不能用扩展欧几里德求出A^j
    我们考虑一个重要的性质：Ad mod Bd = Cd等价于A mod B = C
    因此我们考虑对于gcd(A,p)!=1的情况，我们可以暴力消因子
    我们考虑A^x mod p=B
    我们不断的求出gcd(A,p)直到(A,p)=1为之，令t=gcd(A,p)
    如果B mod t!=0显然当前方程无解，那么对应的原方程也无解
    我们令总共消掉的数为D，那么消完后的方程等价于(A/D)^x mod (p/D) = B/D
    然而这样子做对于A/D还需要求解逆元然后就不好做了
    我们这样做：（参考：https://oi.abcdabcd987.com/bsgs/）

    D = 1, cnt = 0
    while gcd(A, p) != 1:
    if (B % gcd(A, p) != 0)
        No Solution
    B /= gcd(A, p)
    p /= gcd(A, p)
    D *= A / gcd(A, p)
    cnt += 1

    那么之后的方程就变成D*A^(x-cnt) mod p=B（注意此时的B,p对应消过因子的后的数）
    此时gcd(D,p)=1就可以用BSGS求出x-cnt，然后加上cnt即可

    但是上述的方法其实是存在bug的
    我们求出的x-cnt>=0，因此x>=cnt，那么x<cnt的解怎么办？
    我们知道cnt最多为p中2的个数，因此cnt是O(log p)级别的，我们暴力枚举这一部分的情况即可
【一个很实用的trick】：
    我们考虑质数版BSGS
    我们不妨令x=C*i-j (1<=i<=p/C)
    那么(A^C)^i mod p=B*A^j，我们可以预处理出B*A^j，然后map即可
    然后这样似乎没什么大的改进？真的吗？你会求逆矩阵吗，反正我是不会
    我们看一下这题：bzoj 4128: Matrix
    我们利用这个trick，既不用逆矩阵，也不用hash，直接裸上map即可
    不过这么实用的技巧为啥很少人用捏？
【总结】：
    简言之，BSGS在求解一类高次同余问题中是非常实用的
    而它也可以与各种其他的东西相结合
    我们需要针对不同的题目实用不同的做法
    当然extend版的BSGS是非常实用的东西
    就这样了...
    （下面是一些例题）

阅读更多……

【题目大意】：
    有一堆管道，还有一个蜘蛛Willy，如下图所示。所有管道的是上端开口，下端封底，直径都是1cm，连接两个管道的连接容量无限，但体积可以忽略不计。

    在第一个管道上方有一个水源，从中有水不断往下流，速度为每秒0.25 cm3。由于管道横截面积为0.25 cm3，所以单给一个管道注水时水面每秒上升1cm。根据物理知识，在前2秒中，水注如左边的管道底部，第3~5秒时注入右边的管道，第6~9秒同时注入两个管道（虽然流量不变，但是由于同时给两个管道注水，因此水面上升的速度仅为每秒0.5cm），接触到蜘蛛。 给出管道和管道之间连接的位置，以及蜘蛛Willy的位置，求水面接触到Willy的时间。假设蜘蛛的实际位置比给出的略高一点，因此如果蜘蛛在左边管道的n=4的位置，答案应该是5秒。因为前两秒后水面虽然看起来接触到了Willy，但实际上比Willy略低一点。
【题目解法】：
    不明白为啥这么少人AC，弄得我还以为是神题呢TAT
    按照时间模拟显然
    由于所有坐标都是整数，因此水面只有在上升1cm后才有可能碰到蜘蛛，又因为每次有相同高度并且联通的管道每秒钟的数量是平分的，因此我们只需要每次找到最低的若干个相连（必须还有与水源所在管道相连）管道，同时注入1cm水即可
    所以我们开一个数组记录每个管道在这一次灌水中是否能被灌入
    我们从上一次已经灌了水的管道开始bfs，每次bfs与之相连的管道，判断水的高度是否漫过了连接处，如果是则把这个管道标记一下，然后加入队列继续bfs即可
    对于找到的管道，每次找最低的，然后做以下讨论
    1.蜘蛛所在的管道最低并且已经碰到了蜘蛛，输出此时的时间即可，否则跳转2
    2.最低的管道已经满处了管道口，之后的水会源源不断的流到外面，因此水面都不可能在长高，输出无解，否则跳转3
    3.给所有最低的水面同时+1，然后时间相应加上若干即可

阅读更多……

【题目描述】：
    T国有N个城市，用若干双向道路连接。一对城市之间至多存在一条道路。
    在一次洪水之后，一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况，但直到现在几乎没有消息传回。
    幸运的是，此前T国政府调查过每条道路的强度，现在他们希望只利用这些信息估计灾情。具体地，给定每条道路在洪水后仍能通行的概率，请计算仍能通行的道路恰有N-1条，且能联通所有城市的概率。
【题目解法】：
    我们考虑类比无向图的最小生成树算法，得到它的扩展：
    1.令g[i][j]表示(i,j)边的权值
    2.令g[i][i]=-sigma(g[i][j]) i!=j
    那么n-1阶主子式的相反数就是：每个生成树边权乘积之和

    但是这题如果直接这样做的话不能保证其他的边不再树上
    因此我们需要对每一种方案乘上其他边不在树上的概率
    也就是(引用自zky's blog)：

    然后我们可以令原来的边权p[i][j]=p[i][j]/(1-p[i][j])
    最后答案再乘上所有(1-p[e])的乘积（注意双向边只能乘一次）
    证明的话：
    1.如果一个边e被选了，显然他对答案的贡献为p[e]/(1-p[e])*(1-p[e])=p[e]
    2.如果e不被选，那么它对答案的贡献就是(1-p[e])
    细节的话：如果一个1-p[e]等于0，把它当成eps计算即可

阅读更多……