Submission #1162849

---

Source Code Expand

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

const int mod = (int)1e9 + 7;
const int N = 2005;

int f[N][N], d[2*N][N];

int main() {
	int a, b, k;
	cin >> a >> b >> k;
	if (!a || !b) {
		cout << 1 << endl;
		return 0;
	}
	for (int i = 0; i <= a; ++i) {
		for (int j = 0; j <= b; ++j) {
			if (!i && !j) {
				f[i][j] = 1;
				d[i][j] = 1;
				continue;
			}
			int start = i - min(i, k - 1);
			int finish = i - max((k - 1) - j, 0);
			if (finish >= start && (i + j - (k - 1)) >= 0) {
				f[i][j] = (f[i][j] + d[i + j - (k - 1)][finish]) % mod;
				if (start > 0) {
					f[i][j] = (f[i][j] + (mod - d[i + j - (k - 1)][start-1])) % mod;
				}
			}
			d[i + j][i] = f[i][j];
			if (i > 0) {
				d[i + j][i] = (d[i + j][i] + d[i + j][i - 1]) % mod;
			}
		}
	}
	int result = 0;
	for (int x = 0; x <= a; x += k - 1) {
		for (int y = 0; y <= b; y += k - 1) {
			int i = a - x;
			int j = b - y;
			int start = i - min(i, k - 1);
			int finish = i - max(k - j, 1);
			if (finish >= start && (i + j - k) >= 0) {
				result = (result + d[i + j - k][finish]) % mod;
				if (start > 0) {
					result = (result + (mod - d[i + j - k][start-1])) % mod;
				}
			}
		}
	}
	cout << result << endl;
	return 0;
}

Submission Info

Judge Result