题目地址：http://codeforces.com/contest/479/problem/e
这题的动态转移方程很好想，但是最显然的是k*n*n的复杂度，明显不可以。于是就想到了用线段树来维护dp信息，但是仅仅k*n就已经濒临tle了。。在加上个log就会tle了，于是也不行。上网搜了一下才发现用个前缀和的小技巧就可以。= =！用了好多次了居然没有想到。。。。智商捉急。。于是剩下的就很简单了。
本来还想着，不可能走到b的另一侧，于是就只算一侧就可以了。。但是写起来才发现。。只算一侧还不如两侧一块算的代码短。。于是就一块算了。
代码如下：
#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define ll __int64const ll mod=1e9+7;ll dp[6000], sum[3][6000];int main(){ ll n, a, b, k, i, j; while(scanf(%i64d%i64d%i64d%i64d,&n,&a,&b,&k)!=eof) { memset(dp,0,sizeof(dp)); memset(sum,0,sizeof(sum)); dp[a]=1; for(i=a;ib) { dp[j]=(sum[i+1&1][n]+mod-sum[i+1&1][(j+b)/2]+mod-dp[j])%mod; } sum[i&1][j]=(sum[i&1][j-1]+dp[j])%mod; //printf(%i64d ,dp[j]); } //puts(); } printf(%i64d\n,sum[k&1][n]); } return 0;}