设状态$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),虽然看上去很慢

所谓$O(n*m^2)$和$O(n^2*m)$的区别……

STL大法好QAQ

拖延症晚期...现在才改对

Splay总是打错......自己还是弱啊......
SBT打错......Splay大法好退Treap,SBT保平安

竟然毁在M，N上了

COGS 居然不让用 mmap，让卡常大军退散。

回复 @Satoshi :
orzzzzzzzzzzzzzzzzzzzzzzzzzzz

new ioer 跟我代码差不多，我还少了一个循环，我们都写了fread，怎么我刷了几十次还刷不到rank1？

每次对每列判断可行性
一列中两个字母都确定就可以确定第三个字母。

回复 @Satoshi :
Orz

我只想说深夜写代码就是不行，de 和dee dfs时 把m当n使了。。。难怪最后老出事

这数据范围有鬼吧

数据真的没问题吗。。。

回复 @阿努比斯神殿��老魔术羊 :
一年之前的评论你还回什么= =这位学长都滚粗了

%%%

%%%