这题的题目长度成功在茫茫题海中吸引了我

啊哈哈……用两种方法AC了

NC了。。
一直按最大费做的，结果是调了3小时死活过不了样例，无奈%了%别人的代码，才发现问题...哭倒在厕所。。

两种优化

说好的y<x呢！

勒让德定理
对于任意质数p，n！中有（n/p+n/p^2+n/p^3+...)个质因子p

区间DP QAQ

神犇的常数比我小的不知道到哪里去了

楼上正解

此题不挂表非好汉

有一个数据太坑了，一个点好多钥匙...

最终还是走上了打表的不归路

好黑暗的一题

论数组开重的后果……

设状态$f(n,t)$为已经进行了t轮且得分为n的游戏方案数，则可以动态规划:
$f(0,0)=1 \\$
$f(n,t)=\sum_{}^{n-k<=x<=n+k} {f(x,t-1)}$
第二维可以用滚动数组优化，转移可以用前缀和优化,由于如果每次得分都达到了-k或者k，总得分上限为$kt$,所以空间复杂度为$O(kt)$,时间复杂度为$O(kt^2)$
设$g(n)=f(n,T)$.$delta=b-a$则如果小A想要战胜小B，得分必须严格大于$delta$,所以我们枚举小A小B的得分，则$ans=\sum_{i}^{-kt<=i<=kt}\sum_{j}^{i-j>delta} {g(i)g(j)}$。
如果预处理$sum(i)=\sum_{i}^{-kt<=i<=kt}g(i)$(也是一个前缀和),则优化为$ans=\sum_{i}^{-kt<=i<=kt}g(i)*sum(i-delta-1)$。
至于转移时出现的负数平移坐标轴即可.

题解转载：http://blog.csdn.net/ametake/article/details/49280437

手残复制了一句if然后就忘了改变量名了，然后就各种wa了QAQ

一发RMQ, O(NlglgN)-O(lglgN),虽然看上去很慢