Trying to brute-force all possible sequences exceeds the time limit by far, as there are \(M^N\) kinds of possible sequences.

Let’s try determining the sequence from the head. Note the following fact:

• When we determine the sequence from the head, we only have to remember the sum of elements so far; we can discard the details on what each value has been.

Due to the fact, the problem can be solved with Dynamic Programming (DP).

The definition of DP

\(\mathrm{dp}[i][j]:=\) the number of ways to determine the first \(i\) terms of the sequence with the sum \(j\)

Since \(i\) and \(j\) are in the range of \(0\) between \(N\) and \(1\) between \(K\) (inclusive), respectively, there are \(\mathrm{Ο}(NK)\) states in total.

The initial value of DP

First of all, let \(\mathrm{dp}[0][0] = 1\) and fill the remaining elements with \(0\).

The transition of DP

Compute in the increasing order of \(i\). For \(j = 1, \ldots, K-1\) and \(k = 1,\ldots,M\),

• If \(j + k \leq K\), add \(\mathrm{dp}[i][j]\) to \(\mathrm{dp}[i+1][j + k]\).

Answer

Finally, the answer is \(\mathrm{dp}[N][1] + \mathrm{dp}[N][2] + \ldots + \mathrm{dp}[N][K]\).

The computational complexity is \(\mathrm{Ο}(NMK)\).

Sample code (C++):

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using mint = atcoder::modint998244353;

int main() {
	int n, m, K;
	cin >> n >> m >> K;

	vector dp(n + 1, vector(K + 1, mint(0)));
	dp[0][0] = 1;

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < K; j++) {
			for(int k = 1; k <= m; k++) {
				if(j + k <= K) dp[i + 1][j + k] += dp[i][j];
			}
		}
	}

	mint res = 0;
	for(int i = 1; i <= K; i++) {
		res += dp.back()[i];
	}

	cout << res.val() << endl;
}

Bonus 1

Solve it in an \(\mathrm{Ο}(NK)\) time. (For intermediate programmers)

Method

The editorial adopts distributing DP; we consider receiving DP instead.

Here, $\mathrm{dp}[i + 1][j]$ can be expressed by some integers$L,R$ $(L\leq R)$ as

$\mathrm{dp}[i + 1][j] = \mathrm{dp}[i][L] + \ldots + \mathrm{dp}[i][R]$.

since this is in the form of segment sum, we can precalculate the cumulative sums of $\mathrm{dp}[i]$ before updating $\mathrm{dp}[i+1]$, so that the transition can be done in an $\mathrm{Ο}(1)$ time.

Therefore, the problem has been solved in a total of $\mathrm{Ο}(NK)$ time. The optimization of DP using cumulative sums are frequently used, so it is worth learning.

Bonus 2

Solve it in an \(\mathrm{Ο}(K)\) time. (For advanced programmers)

Method

We use formal power series.

Let $f(x)=x + x^2 + \ldots + x^ M = x \frac{1-x^M}{1-x}$; then the answer is the sum of coefficients of $f(x)^N$ from the $1$-st through $K$-th degrees.

Since the sum of coefficients of $f(x)$ from the $1$-st through $K$-th degree is equal to the coefficient of $f(x)/(1-x)$ of $K$-th degree, it is sufficient to find the coefficient of the $(K-N)$-th degree of $(1-x^M)^{N}(1-x)^{-(N+1)}$.

The coefficient of each term of $(1-x^M)^{N}$ can be computed in an $O(K)$ time using binomial coefficients. Also, the coefficient of each term of $(1-x)^{-(N+1)}$ can be computed in an $O(K)$ time using negative binomial coefficients (we don't explain them in details; search in the Internet if you are interested in) too.

Therefore, the problem has been solved in a total of $\mathrm{Ο}(K)$ time. The optimization of combinatoric problems using formal power series is occasionally found in difficult problems, so we recommend learning if you are interested in.