51nod算法马拉松23（飞越愚人节）

这是拖了多久的题解…什么时候我也有拖延症了..

A. 不会..

B. 设生成的数和的期望为 f ，n个数的平均数为x 那么有 f=x+(1−mn)f 所以 f=x∗nm

C. 可以发现，一条路径上两个不同的城市x,y的a[x] mod a[y]的最大值即是a的次大值，于是只要求出首都到每个城市所有路径次大值的最大值 先缩环，然后做一个拓扑排序，维护到每个点的所有路径的最大值，次大值，每个点的答案， 对于一条边 x−>y ，若 ansy≠ansx ， 则要么 x 环的最大值作为路径上的次大值贡献到答案， 要么x环上的最大值作为路径上的最大值，到 y 的路径上的最大值作为路径上的次大值贡献到答案， 或者最大值相等，两者次大值的较大值贡献到答案

D. 求最短路为i的方案数，考虑到每次不能往左走，而且行数 n 很小，可以考虑从左到右做一个状压DP，因为要维护最短路为i的方案数，又易知相邻点的最短路差 ≤1 ，可以定义状态 f[i][k][l] 为DP到第 i 列第n行最短路为k，一个三进制数 l 表示第n−1∽1行和上一行最短路的差分值，搜索预处理一下状态之间的转移，第一维滚动就行了

E. 绝对值符号不拆留着过年… 莫队，将绝对值符号拆掉之后，推一下柿子，发现树状数组维护个数、下标和、a[i]的和、i*a[i]的和，就可以 O(logn) 移动两端点，然后卡一下常… 题解是一个很玄妙的分块？感觉常数和一个log也不会差太远…

F. 用到了洲阁筛的思想吧，挺厉害的一个DP（详见官方题解吧…）