質問アドレス: http://codeforces.com/contest/479/problem/E
この質問の動的伝達方程式は非常に興味深いものですが、最も明らかなことは、k*n*n の複雑さは明らかにありえない。そこで、DP情報を維持するために線分ツリーを使用することを考えましたが、k*nだけがすでにTLEの寸前にあります。 。ログを追加するとTLEが発生するため動作しません。インターネットで調べてみると、prefix sum を使うというちょっとした裏技が使えることが分かりました。 = =!何度も利用していますが、考えたこともありませんでした。 。 。 。 IQが低い。 。したがって、残りは簡単です。
元々bの反対側まで歩くのは無理だと思っていたので片側だけ数えました。 。でも書くまで気づきませんでした。 。片側だけを数えるのは、両側を数えるほど短くはありません。 。だから忘れてください。
コードは次のとおりです:
#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>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;i<=n;i++) sum[0][i]=1; for(i=1;i<=k;i++) { sum[i&1][0]=0; for(j=1;j<=n;j++) { if(j<b) { dp[j]=(sum[i+1&1][(j+b-1)/2]+mod-dp[j])%mod; } else if(j>b) { 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;}
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
