Submission #1084574

---

Source Code Expand

#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

typedef long long i64;

const int NMAX = 2005;
const int MOD = (int) 1e9 + 7;

int dp[NMAX][NMAX];
int pow2[NMAX];

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    pow2[0] = 1;
    for (int i = 1; i <= n; ++i) {
        pow2[i] = 2 * pow2[i - 1] % MOD;
    }

    dp[n][0] = 1;
    dp[n][1] = -1;
    int ans = 0;
    for (int i = n; i >= 0; --i) {
        for (int j = 1; j <= i; ++j) {
            dp[i][j] += dp[i][j - 1];
            dp[i][j] %= MOD;
        }
        if (n - i == k || i == 1) {
            ans = (int64_t) dp[i][i - 1] * pow2[i - 1] % MOD;
            break;
        } else {
            for (int j = 0; j < i - 1; ++j) {
                dp[i - 1][j] += dp[i][j];
                dp[i - 1][j] %= MOD;
                dp[i - 1][i] -= dp[i][j];
                dp[i - 1][i] %= MOD;
            }
            for (int j = 1; j < i; ++j) {
                dp[i - 1][j - 1] += dp[i][j];
                dp[i - 1][j - 1] %= MOD;
                dp[i - 1][j] -= dp[i][j];
                dp[i - 1][j] %= MOD;
            }
        }
    }
    ans %= MOD;
    if (ans < 0) ans += MOD;
    cout << ans << '\n';
}

Submission Info

Judge Result