lh大神的期中考

OI - Official

From shineFlyorzlhcenyk1230


小时

尚未报名

萌萌的物理考试 9/21 From
萌萌的数学考试 3/15 From
萌萌的英语考试 8/18 From

最近三天是大型灾难片期中考,这是一个关于LH神犇的故事。

题解:

萌萌的物理考试:
其实就是要求1^m+2^m+3^m+...+n^m
记Sm=1^m+2^m+3^m+...+n^m我们发现可以通过S1,S2,...Sm-1计算Sm
通过将(x+1)^m二项式展开,然后将x=1,2,3...的等式相加,两边消去同类项可以得到一个关于S1,S2,..Sm-1的等式
通过这个等式就可以求了,复杂度为O(m^2*q)(不含预处理)
比赛中sunzhouyi,xyz111两位神犇似乎使用了O(m*q)(不含预处理,目测)的算法,求指点。

萌萌的数学考试:
此题改编自SDOI 2013 Round1 Day1 随机数生成器,所以算法也大致相同。
SDOI 2013 Round1 Day1 随机数生成器的方法在题目中给出,我们可以将Yi变成一个矩阵,神牛看到这里应该就会了吧。
接下来是完整算法,另初始解写成的向量为A,目标向量为T,变换为矩阵Y,b=sqrt(p^n),我们预处理出T*Y^k(k<=b),
接下来从小到大枚举i<=b,寻找一个t,使得A*Y^(i*b)=B*Y^t(mod p),那么i*b-t+1就是答案了。
至于为什么是b=sqrt(p^n),因为在如果有解,解必定在p^n范围内。
详细实现见标程,不过似乎有点长O_O

萌萌的英语考试:
显然这是一个把两道题强行凑在一起的行为,先处理字符串两两之间的最大重合部分,然后进行状态压缩DP。
对于第一个问题,标程给出了一种利用AC自动机处理的方法,显然KMP和hash可以处理这个问题,但对于字符串之间的包含情况需要特别注意,众神犇的程序显然虐了标程。
对于第二个问题,采用2进制记录点的包含情况,在转移时不需要使用类似SPFA的松弛方法,可以直接从小到大枚举状态。提交中Revain提交了使用费用流的做法,很出人意料得取得了70分的成绩(本来我目测只有40分的,STQ),实际应该是错误的方法,但本蒟蒻无法证明T-T,欢迎BS。