Submission #4314458

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int64_t MOD = 1e9+7;
void add(int64_t& a, int64_t b){
     a = (a+b) % MOD;
}

int main(){
    int N, K;
    cin >> N >> K;

    int64_t pow2[5002];
    pow2[0] = 1;
    for(int i=1; i<=5001; i++) pow2[i] = pow2[i-1] * 2 % MOD;

    static int64_t dp[5002][5002];
    dp[0][0] = 1;

    for(int i=1; i<=N-K; i++){
        int64_t sum = dp[i-1][i-1];
        for(int j=i; j<=N; j++){
            dp[i][j] = dp[i-1][j] * pow2[max(0, j-i-K+1)] % MOD;
            if(j-i-K >= 0) add(dp[i][j], sum * pow2[j-i-K]);
            add(sum, dp[i-1][j]);
        }
    }

    cout << dp[N-K][N] << endl;
    return 0;
}

Submission Info

Judge Result