Submission #1293459

---

Source Code Expand

#include <cstdio>
typedef long long int64;
static const int MAXN = 2003;
static const int MODULUS = 1e9 + 7;
#define _  %  MODULUS
#define __ %= MODULUS

int binom[MAXN * 2][MAXN * 2] = {{ 0 }};
inline void preprocess_binomials()
{
    binom[0][0] = 1;
    for (int i = 1; i < MAXN * 2; ++i) {
        binom[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j])_;
    }
}
inline int fpow(int64 base, int exp)
{
    int64 ans = 1;
    for (; exp; exp >>= 1, (base *= base)__) if (exp & 1) (ans *= base)__;
    return ans;
}
inline int catalan(int n) { return (int64)binom[2 * n][n] * fpow(n + 1, MODULUS - 2)_; }

int n, k;
// f[# of total elements][# of red elements] - nnumber of ways to distribute to two sides
int f[MAXN * 2][MAXN * 2] = {{ 0 }};

inline void preprocess_transitions()
{
    f[0][0] = 1;
    for (int i = 0; i < MAXN * 2 - 1; ++i) {
        f[i + 1][0] = f[i][0];
        for (int j = 1; j <= i + 1; ++j)
            f[i + 1][j] = (f[i + 1][j - 1] + f[i][j])_;
    }
}

int main()
{
    preprocess_binomials();
    scanf("%d%d", &n, &k);
    if (n == k) { printf("%d\n", catalan(n - 1)); return 0; }

    preprocess_transitions();
    int64 ans = 0;
    for (int m = n - k + 1; m <= n; ++m) {
        int akai = n - m, aoi = m - 1 - (n - k);
        int64 inc = f[akai + aoi][akai];
        (inc *= binom[m - 2][n - k - 1])__;
        (inc *= fpow(2, n - k - 1))__;
        ans += inc;
    }
    printf("%lld\n", ans _);

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:43:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &k);
                          ^

Judge Result