Submission #1771364

---

Source Code Expand

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

const int mod = 1000*1000*1000+7;

int N, M, K;

vector<vector<int> > cc;
int dp(int t, int m) {
    if(t == -1) return 0;
    int &ret = cc[t][m];
    if(ret != -1) return ret;

    ret = m != M && m % (K - 1) == 0 && m / (K - 1) == t;
    for(int i = 0; i < K; i++) {
        if(i <= m) {
            ret += dp(t - 1, m - i);
            ret %= mod;
        }
    }

    //cout << t << ' ' << m << ' ' << ret << endl;

    return ret;
}

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

    cc = vector<vector<int> >((N + M - 1) / (K - 1) + 1, vector<int>(M + 1, -1));
    cout << dp((N + M - 1) / (K - 1), M);
}

Submission Info

Judge Result