Submission #1076479

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;
const ll MOD = 1e9 + 7;
const ll MX = 4010;

ll dp[MX];
ll dp2[MX];

int main() {
	int n, m, k;
	cin >> n >> m >> k;
	int k2 = k - 1;
	ll ans = 0;
	dp[0] = 1;
	int it = (n + m - 1) / k2;
	for (int i = 1; i <= it; ++i) {
		for (int j = 0; j <= m; ++j)
			dp2[j] = 0;
		for (int j = 0; j <= m; ++j) {
			for (int l = 0; l < k && j + l <= m; ++l)
				dp2[j + l] = (dp2[j + l] + dp[j]) % MOD;
		}
		for (int j = 0; j <= m; ++j)
			dp[j] = dp2[j];
		for (int j = 1; j <= m; ++j) {
			int x = j;
			int y = i * k2 - x;
			++y;
			if (m >= x && (m - x) % k2 == 0 && n == y) {
				ans = (ans + dp[j]) % MOD;
			}
		}
	}
	cout << ans << "\n";
	return 0;
}

Submission Info

Judge Result