题目名称	2462. [Codeforces 712D] 随机数游戏
输入输出	`randomgame.in/out`
难度等级	★☆
时间限制	2000 ms (2 s)
内存限制	32 MiB
测试数据	10
题目来源	Satoshi 于2016-09-12加入
开放分组	全部用户
提交状态
分类标签	Codeforces
	分享题解

通过：2，提交：2，通过率：100%
_Itachi	100	5.393 s	3.34 MiB	C++
Satoshi	100	5.733 s	18.62 MiB	C++

关于随机数游戏的近10条评论(全部评论)
回复 @Satoshi : %%%,果然CF都是些只有大神才想得出的DP。。 _Itachi 2016-11-11 08:01 8楼
回复 @BillAlen : 故意的...... Satoshi 2016-09-30 03:53 7楼
回复 @BillAlen : 也只有真正的粉丝。。。 Janis 2016-09-23 10:25 6楼
取膜……能不能别打错字…… BillAlen 2016-09-22 20:30 5楼
设状态$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)$。至于转移时出现的负数平移坐标轴即可. Satoshi 2016-09-15 20:16 4楼
回复 @Satoshi : orzzzzzzzzzzzzzzzzzzzzzzzzzzz AntiLeaf 2016-09-15 13:52 3楼
回复 @Satoshi : Orz 沉迷学习的假的Keller 2016-09-15 09:18 2楼
%%% AntiLeaf 2016-09-14 12:07 1楼

2462. [Codeforces 712D] 随机数游戏

★☆ 输入文件：randomgame.in 输出文件：randomgame.out 简单对比
时间限制：2 s 内存限制：32 MiB

【题目描述】

小A和小B用C++的rand()函数玩随机数游戏，刚开始小A有a分，小B有b分，每一轮游戏两个人使用rand()函数生成一个$[-k,k]$之间的整数作为得分(比如k=2的时候可能会生成-2,1,0,1,2)，游戏一共进行T轮，求总共有多少种不同的游戏使得小A的最终得分大于小B？两个游戏不同当且仅当至少有一轮存在一个人的得分不同。

【输入格式】

只有一行四个数字，为a,b,k,T

【输出格式】

只有一行一个数字，为答案对$10^9+7$取膜后的值

【样例输入1】

1 2 2 1

【样例输出1】

【样例输入2】

1 1 1 2

【样例输出2】

【提示】

In the first sample test, A starts with 1 and B starts with 2. If B picks - 2, A can pick 0, 1, or 2 to win. If B picks - 1, A can pick 1 or 2 to win. If B picks 0, A can pick 2 to win. If B picks 1 or 2, A cannot win. Thus, there are 3 + 2 + 1 = 6 possible games in which A wins.

对于20%的数据,$T<=3$

对于60%的数据,$k<=100,T<=50$

对于100%的数据,$0<=a,b<=10^6,k<=1000,T<=100$

【来源】

CF 712D