Official Analysis (C++)

Explanation

Let $\texttt{dp[a]}$ be the number of ways to achieve the sum $a$ using the current set of balls. We'll update our array dynamically as balls are added or removed.

If we add a ball with value $x$, we loop over all $j$ from $K$ to $x$ while performing the following transition:

An important thing to note is that we have to iterate backward; otherwise we might add this one ball multiple times.

To remove a ball of value $x$, we do the same thing, but in reverse. This entails going from $x$ to $K$ and decrementing instead of incrementing.

Implementation

Time Complexity: $\mathcal{O}(QK)$

Copy
#include <iostream>
#include <vector>

const int MOD = 998244353;

int main() {
	int q, k;
	std::cin >> q >> k;

	std::vector<long long> dp(k + 1);

Copy
import java.io.*;
import java.util.*;

public class Main {
	private final static int MOD = 998244353;
	public static void main(String[] args) {
		Kattio io = new Kattio();

		int q = io.nextInt();
		int k = io.nextInt();

Copy
MOD = 998244353

q, k = map(int, input().split())
dp = [0] * (k + 1)

dp[0] = 1

for i in range(q):
	a = input().strip()
	t, x = a.split()