Memory and Scores CodeForces - 712D【好题啊！！】

题意：A和B两个人的初始积分为a,b。每一轮A,B均可从[-k,k]的区间内取出一个数，累加在初始积分上，共执行t轮，问A赢B的有多少种可能。

思路：暴力复杂度O(t*kt*k) TLE 。 取dp前缀和优化，每次的前缀和为下次的前缀和服务，以此类推。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int MOD=1e9+7;
const int maxn=1e5+1e5+9000;
int dp [101][maxn];
int dp1[101][maxn];
int  pre[101][maxn];

int main(void)
{
    memset(pre,0,sizeof(pre));
    memset(dp,0,sizeof(dp));
    int a,b,k,t;
    cin >> a >> b >> k>> t;
    int shift=1e5+2*k;
    dp[0][a+shift]=1;
    for(int i=a+shift;i<=maxn;i++)  pre[0][i]=pre[0][i-1]+dp[0][i];
    for(int i=1;i<=t;i++)
    {
        for(int j=a-k*t+shift;j<=a+k*t+shift;j++)
        {
            dp[i][j]=(pre[i-1][j+k]-pre[i-1][j-k-1]+MOD)%MOD;
            //printf("dp[%d][%d]=%d %d %d\n",i,j-shift,dp[i][j],pre[i-1][j+k],pre[i-1][j-k-1]);
        }
        for(int j=a-k*t+shift;j<=a+k*t+shift+k;j++)
        {
            pre[i][j]=(1LL*dp[i][j]%MOD+1LL*pre[i][j-1])%MOD;
        }
    }

   /* for(int i=0; i<=t; i++)
    {
        for(int o=0; o<=maxn; o++)
        {
            if(dp[i][o])
                printf("fs=%d --- cs=%d ",o-shift,dp[i][o]);
        }
        puts("");
    }*/
    memset(pre,0,sizeof(pre));
     dp1[0][b+shift]=1;
    for(int i=b+shift;i<=maxn;i++)  pre[0][i]=pre[0][i-1]+dp1[0][i];
    for(int i=1;i<=t;i++)
    {
        for(int j=b-k*t+shift;j<=b+k*t+shift;j++)
        {
            dp1[i][j]=(pre[i-1][j+k]-pre[i-1][j-k-1]+MOD)%MOD;
            //printf("dp1[%d][%d]=%d %d %d\n",i,j-shift,dp1[i][j],pre[i-1][j+k],pre[i-1][j-k-1]);
        }
       for(int j=b-k*t+shift;j<=b+k*t+shift+k;j++)
        {
            pre[i][j]=(1LL*dp1[i][j]%MOD+1LL*pre[i][j-1])%MOD;
           // printf("pre[%d][%d]=%d %d %d\n",i,j-shift,pre[i][j],dp1[i][j],pre[i][j-1]);
        }
    }
    /*for(int i=0; i<=t; i++)
    {
        for(int o=0; o<=maxn; o++)
        {
            if(dp1[i][o])
                printf("fs=%d --- cs=%d ",o-shift,dp1[i][o]);
        }
        puts("");
    }*/
    ll ans=0;
    for(int i=-1e5;i<=1e5+5000;i++)
    {
        pre[t][i+shift]=(1LL*pre[t][i+shift-1]%MOD+1LL*dp1[t][i+shift]%MOD)%MOD;
    }
    for(int i=-1e5;i<=1e5+5000;i++)
    {
        ll sum=0;
        if(dp[t][i+shift])
        {
            ans=(1LL*ans%MOD+1LL*dp[t][i+shift]%MOD*pre[t][i+shift-1]%MOD)%MOD;
        }
    }
   cout << ans << endl;
}

//这题我数了一下，WA/TLE 了 16 发 。 菜的一批。 错了两天，终于A了。。。。。。。。。。。。
出现的问题有:
1.对相减的两个数，先减再mod和先mod再减是不一样的东西。
2.坐标平移要注意到越界的问题。
3.对于范围比较大的 ， 注意 1LL* 变成long long 再搞，再赋值给long long 类型的变量。