Submission #1075748

---

Source Code Expand

//#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

//ifstream cin("tema.in");
//ofstream cout("tema.out");

const int MAXN = 4000;
const int MOD = 1000000007;

int dp[1 + MAXN][1 + MAXN], sum[1 + MAXN][1 + MAXN];

void Count(int ones, int digits, int base) {
    for (int i = 0; i <= min(ones, base - 1); i++) {
        dp[0][i] = 1;
        sum[0][i] = i + 1;
    }
    for (int i = base; i <= ones; i++)
        sum[0][i] = sum[0][i - 1];
    for (int i = 1; i < digits; i++)
        for (int j = 0; j <= ones; j++) {
            dp[i][j] += sum[i - 1][j];
            if (dp[i][j] >= MOD)
                dp[i][j] -= MOD;
            int k = j - min(base - 1, j) - 1;
            if (k >= 0) {
                dp[i][j] -= sum[i - 1][k];
                if (dp[i][j] < 0)
                    dp[i][j] += MOD;
            }
            sum[i][j] = dp[i][j];
            if (j) {
                sum[i][j] += sum[i][j - 1];
                if (sum[i][j] >= MOD)
                    sum[i][j] -= MOD;
            }
        }
}

int main() {
    int n, m, k, answer = 0;
    cin >> n >> m >> k;
    Count(m, (n + m - 1) / (k - 1), k);
    while (m > 0) {
        answer += dp[(n + m - 1) / (k - 1) - 1][m];
        if (answer >= MOD)
            answer -= MOD;
        m -= (k - 1);
    }
    cout << answer << "\n";
    return 0;
}

Submission Info

Judge Result