Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của happyboy99x

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

const int N = 2000, MOD = 1000000009;
long long f[N+1][N+1];
int n, k;

int main() {
    cin >> n >> k;
    fill(f[0], f[0]+k+1, 1);
    for(int i = 1; i <= n; ++i) {
        f[i][0] = 1;
        for(int j = 1; j <= k; ++j) {
            int mn = j-i+1 + max(0, i-j-1);
            f[i][j] = (f[i][j-1] + f[i-1][j] - (mn == 0 ? 0 : f[i-1][mn-1])) % MOD;
        }
    }
    long long res = 0;
    for(int j = k; j >= 0; j -= 2)
        res = (res + f[n][j] - (j == 0 ? 0 : f[n][j-1])) % MOD;
    cout << (res + MOD) % MOD << '\n';
    return 0;
}

Code mẫu của ladpro98

#include <cstdio>
const int N = 2020;
const int MOD = 1000000009;
using namespace std;
int n, k;
int F[N][N];

int main() {
    scanf("%d %d", &n, &k);
    F[1][0] = 1;
    int parity = k & 1;
    for(int i = 2; i <= n; i++)
    for(int j = 0; j <= k; j++) {
        F[i][j] = (F[i][j - 1] + F[i - 1][j]) % MOD;
        if (j >= i) F[i][j] = (F[i][j] + MOD - F[i - 1][j - i]) % MOD;
    }
    int res = 0;
    for(int j = parity; j <= k; j += 2)
        res = (res + F[n][j]) % MOD;
    printf("%d", res);
    return 0;
}

Code mẫu của RR

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
using namespace std;

const int MOD = (int) (1e9 + 9);

int f[2011][2011], s[2011];
int n, k;

int main() {
    while (cin >> n >> k) {
        if (n == 1) {
            if (k == 0) cout << 1 << endl;
            else cout << 0 << endl;
            continue;
        }

        memset(f, 0, sizeof f);

        FOR(j,0,k) f[2][j] = 1;
        FOR(i,3,n) {
            s[0] = f[i-1][0];
            FOR(j,1,k) {
                s[j] = s[j-1] + f[i-1][j];
                if (s[j] >= MOD) s[j] -= MOD;
            }

            FOR(j,0,k) {
                f[i][j] = s[j];
                if (j >= i) {
                    f[i][j] -= s[j-i];
                    if (f[i][j] < 0) f[i][j] += MOD;
                }
            }
        }
        cout << f[n][k] << endl;
    }
    return 0;
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) {
    stringstream ss;
    if (p >= 0)
        ss << fixed << setprecision(p);
    ss << a;
    T r;
    ss >> r;
    return r;
}
template<class T> T gcd(T a, T b) {
    T r;
    while (b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}
template<class T> T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}
template<class T> T sqr(T x) {
    return x * x;
}
template<class T> T cube(T x) {
    return x * x * x;
}
template<class T> int getbit(T s, int i) {
    return (s >> i) & 1;
}
template<class T> T onbit(T s, int i) {
    return s | (T(1) << i);
}
template<class T> T offbit(T s, int i) {
    return s & (~(T(1) << i));
}
template<class T> int cntbit(T s) {
    return s == 0 ? 0 : cntbit(s >> 1) + (s & 1);
}

const int bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc() {
    if (rsz <= 0) {
        ptr = 0;
        rsz = (int) fread(bf, 1, bfsz, stdin);
        if (rsz <= 0)
            return EOF;
    }
    --rsz;
    return bf[ptr++];
}
void ga(char &c) {
    c = EOF;
    while (!isalpha(c))
        c = gc();
}
int gs(char s[]) {
    int l = 0;
    char c = gc();
    while (isspace(c))
        c = gc();
    while (c != EOF && !isspace(c)) {
        s[l++] = c;
        c = gc();
    }
    s[l] = '\0';
    return l;
}
template<class T> bool gi(T &v) {
    v = 0;
    char c = gc();
    while (c != EOF && c != '-' && !isdigit(c))
        c = gc();
    if (c == EOF)
        return false;
    bool neg = c == '-';
    if (neg)
        c = gc();
    while (isdigit(c)) {
        v = v * 10 + c - '0';
        c = gc();
    }
    if (neg)
        v = -v;
    return true;
}

typedef pair<int, int> II;
const ld PI = acos(-1.0);
const ld eps = 1e-9;
const int dr[] = { -1, 0, +1, 0};
const int dc[] = { 0, +1, 0, -1};
const int inf = (int) 1e9 + 5;
const ll linf = (ll) 1e16 + 5;
const ll mod = (ll) (1e9 + 9 + eps);
#define ok puts("ok")
#define maxn 2005

int n, m;
ll f[maxn][maxn];

int main()
{
   // freopen("in.txt", "r", stdin);
    cin >> n >> m;
    ms(f, 0);
    f[1][0] = 1;

    For(i, 2, n){
        f[i][0] = 1;
        For(j, 1, m){
            f[i][j] = f[i - 1][j] + f[i][j - 1];
            if(j >= i) f[i][j] = (f[i][j] + mod - f[i - 1][j - i]);
            while(f[i][j] >= mod) f[i][j] -= mod;
        }
    }

    ll res = 0;
    Rep(i, m + 1) if((m - i) % 2 == 0) res = (res + f[n][i]) % mod;
    cout << res << endl;

    return 0;
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   2020
const int mod=(int)1e9+9;
const int ntest=30;
char fi1[]="0.in";
char fo1[]="0.ans";
char fi2[]="00.in";
char fo2[]="00.ans";
int n,k;
int f[MAX][MAX];
int s[MAX][MAX];
int max(const int &x,const int &y) {
    if (x>y) return (x); else return (y);
}
int process(void) {
    scanf("%d",&n);
    scanf("%d",&k);
    //printf("%d %d\n",n,k);
    int i,j;
    if (n==1) return (0);   
    for (i=0;i<=k;i=i+1) {
        f[2][i]=1;
        if (i==0) s[2][i]=f[2][i];
        else s[2][i]=(s[2][i-1]+f[2][i])%mod;
    }
    for (i=3;i<=n;i=i+1)
        for (j=0;j<=k;j=j+1) {
            f[i][j]=0;
            f[i][j]=s[i-1][j];
            if (j-i+1>0) f[i][j]=(f[i][j]-s[i-1][j-i]+mod)%mod;         
            if (j==0) s[i][j]=f[i][j];
            else s[i][j]=(s[i][j-1]+f[i][j])%mod;
        }
    //printf("f(%d,%d)=%d\n",n,k,f[n][k]);
    return (f[n][k]);
}
void checker(void) {
    int nt;
    int ans,res;
    clock_t TLE;
    for (nt=0;nt<=ntest;nt++) {
        if (nt>9) {
            fi2[0]=nt/10+48;
            fi2[1]=nt%10+48;
            fo2[0]=nt/10+48;
            fo2[1]=nt%10+48;
            freopen(fo2,"r",stdin);
            scanf("%d",&ans);
            freopen(fi2,"r",stdin);         
        }
        else {
            fi1[0]=nt+48;
            fo1[0]=nt+48;
            freopen(fo1,"r",stdin);
            scanf("%d",&ans);
            freopen(fi1,"r",stdin);
        }
        TLE=clock()+CLOCKS_PER_SEC*0.7;
        res=process();  
        if (clock()>TLE) {
            printf("Time limit exceeded on test %d\n",nt);
            return;
        }
        //printf("Test Case %d: ",nt);
        /*if (res==ans) printf("Correct\n");
        else printf("Wrong answer\n\tInput: %d %d\n\tExpected: %d\n\tReceived: %d\n",nt,n,k,ans,res);*/
        if (res!=ans) {         
            printf("Wrong answer on test %d\n\tInput: %d %d\n\tExpected: %d\n\tReceived: %d\n",nt,n,k,ans,res);
            return;
        }
    }
    printf("Accepted");
}
int main(void) {
    //checker();    
    printf("%d\n",process());
    return 0;
}