Submission #1078177

---

Source Code Expand

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#include <cstdio>
#include <complex>
#include <cstring>

using namespace std;

const int MOD = (int)1e9 + 7;
const int N = 2000 + 5;

int n, m, k;
int f[N][N];

void solve()
{
    cin >> n;
    cin >> m;
    cin >> k;
    f[0][0] = 1;
    long long ans = 0;
    for(int i = 0; i <= n; ++ i) {
        for(int j = 0; j < m; ++ j) {
            if (f[i][j] == 0) continue;
            //cout << i << ' ' << j << ' ' << f[i][j] << endl;
            for(int ni = 0; ni <= k - 1; ++ ni) {
                int pi = i + ni;
                int pj = j + k - 1 - ni;
                if (pi <= n && pj <= m - 1) {
                    (f[pi][pj] += f[i][j]) %= MOD;
                    if (ni && pi % (k - 1) == n % (k - 1) && pj % (k - 1) == (m - 1) % (k - 1)) {
                        ans += f[i][j];
                        //cout << i << ' ' << j << ' ' << f[i][j] << ' ' << pi << ' ' << pj << endl;
                    }
                }
            }
        }
    }
    cout << ans % MOD << endl;
}

int main()
{
    solve();
    return 0;
}

Submission Info

Judge Result