Codeforces 712 D. Memory and Scores (DP+滚动数组+前缀和优化)

题目链接：http://codeforces.com/contest/712/problem/D

A初始有一个分数a，B初始有一个分数b，有t轮比赛，每次比赛都可以取[-k, k]之间的数，问你最后A比B大的情况有多少种。

dpA[i][j]表示第i轮获得j分的情况数。因为第i轮只和第i-1轮有关，所以这里i用滚动数组优化。

要是普通做法3个for就会超时，所以要用前缀和优化，dpA[i][j]可以由一段连续的dp[i - 1][x]转移过来，所以用sumA数组存取dp[i - 1][x]的前缀和。就可以省去一个for。

B同理。

 //#pragma comment(linker, "/STACK:102400000, 102400000")

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <ctime>

 #include <list>

 #include <set>

 #include <map>

 using namespace std;

 typedef long long LL;

 typedef pair <int, int> P;

 const int N = 2e5 + ;

 LL dp[][N], mod = 1e9 + , sum[N], dpA[][N], sumA[N];

 int main()

 {

     int a, b, k, t;

     scanf("%d %d %d %d", &a, &b, &k, &t);

     a += 1e5, b += 1e5;

     dp[][b] = ;

     dpA[][a] = ;

     sum[b] = , sumA[a] = ;

     for(int i = ; i <= t; ++i) {

         for(int j = ; j < N; ++j) {

             dp[i%][j] = dpA[i%][j] = ;

         }

         for(int j = -k*i; j <= k*i; ++j) {

             int l = max(-k*(i - ), j - k), r = min(k*(i - ), j + k);

             dp[i % ][b + j] = ((sum[r + b] - sum[l -  + b] + dp[i % ][b + j]) % mod + mod) % mod;

             dpA[i % ][a + j] = ((sumA[r + a] - sumA[l -  + a] + dpA[i % ][a + j]) % mod + mod) % mod;

         }

         for(int j = ; j < N; ++j) { //在每轮中sum都会重新更新

             sum[j] = (sum[j - ] + dp[i % ][j]) % mod;

             sumA[j] = (sumA[j - ] + dpA[i % ][j]) % mod;

         }

     }

     LL ans = ;

     for(int i = ; i < N; ++i) {

         ans = (ans + sum[i - ]*dpA[t % ][i] % mod) % mod;

     }

     printf("%lld\n", ans);

     return ;

 }