# diverta 2019 Programming Contest. E - Balanced Piles

We shall explain O(NH) solution by dynamic programming. Suppose that the elements are lined up in ascending order. Consider this operation: choose the leftmost element, and increase it to the old maximum or larger. We repeat this operation until all elements become H.

In the following figure, we chose A and inserted A between I and J. As depicted in this figure, between G and H, between H and I, and after J are also possible. Generally, If there are j maximum elements, there are j+1 places we can insert into. After inserting A, we next insert B into somewhere, and then C, D, E, F ... are followed.

Let dp[i][j] be the number of ways such that the maximum is equal to i and the number of maximum elements is equal to j. Initially,

$dp[0][N]=1.$

As stated above,

$\mathrel{\mathbf{if}} j \ne N \mathrel{\mathbf{then}} dp[i][j+1] \mathrel{{+}{=}} dp[i][j]*(j+1).$

Moreover, we may increase the leftmost element to the strictly larger than i. Thus,

$\mathrel{\mathbf{for}} k=1 \mathrel{\mathbf{to}} D \mathrel{\mathbf{do}} dp[i+k][1] \mathrel{{+}{=}} dp[i][j].$

$dp[H][N].$

Let us speed up this dp. Carefully viewing the releation, we can notice that

$\mathrel{\mathbf{for}} k=1 \mathrel{\mathbf{to}} D \mathrel{\mathbf{do}} dp[i+k][1] \mathrel{{+}{=}} dp[i][1] + dp[i][2] + \cdots + dp[i][N].$

Since $dp[i][j] = j! * dp[i][1]$, we can restate it as follows.

$\mathrel{\mathbf{for}} k=1 \mathrel{\mathbf{to}} D \mathrel{\mathbf{do}} dp[i+k][1] \mathrel{{+}{=}} (1! + 2! + \cdots + N!)*dp[i][1].$

Thus, we can solve this problem in O(N+H) time.

https://atcoder.jp/contests/diverta2019-2/submissions/5931171

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()
using namespace std;
using ll = long long;

const int MOD = 1000000007;

struct mint {
int n;
mint(int n_ = 0) : n(n_) {}
};

mint operator-(mint a) {
return -a.n + MOD * (a.n != 0);
}
mint operator+(mint a, mint b) {
int x = a.n + b.n;
return x - (x >= MOD) * MOD;
}
mint operator-(mint a, mint b) {
int x = a.n - b.n;
return x + (x < 0) * MOD;
}
mint operator*(mint a, mint b) {
return (long long)a.n * b.n % MOD;
}
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }
istream &operator>>(istream &i, mint &a) { return i >> a.n; }
ostream &operator<<(ostream &o, mint a) { return o << a.n; }

void naive() {
static mint dp[50][50];
int N, H, D;
cin >> N >> H >> D;
dp[0][N] = 1;
for (int i = 0; i <= H; i++) {
for (int j = 0; j <= N; j++) {
for (int k = i + 1; k <= min(H, i + D); k++) {
dp[k][1] += dp[i][j];
}
if (j < N) {
dp[i][j + 1] += dp[i][j] * (j + 1);
}
}
}
cout << dp[H][N] << endl;
}

int main() {
int N, H, D;
cin >> N >> H >> D;
mint f = 1;
mint s = 0;
for (int i = 1; i <= N; i++) {
f *= i;
s += f;
}
vector<mint> dp(H + 2); // dp[i][1]
dp[1] += 1;
dp[D + 1] -= 1;
for (int i = 1; i < H; i++) {
dp[i + 1] += dp[i];
int l = i + 1;
int r = min(H + 1, i + D + 1);
dp[l] += dp[i] * s;
dp[r] -= dp[i] * s;
}
mint ans = dp[H] * f;
cout << ans << '\n';
}