Overview

This problem asks us to find the number of non-empty subsets of sweets such that the sum of their calories is a multiple of \(K\).

Instead of focusing on the sum itself, we can perform dynamic programming by focusing only on the “sum modulo \(K\)”.

Approach

If we perform a brute-force search on whether to choose each sweet or not, there are \(2^N\) possible combinations.
Since \(N\) is at most \(2 \times 10^5\), this will not run in time.

The key point here is that the condition is:

\[ \sum_{i \in S} A_i \equiv 0 \pmod K \]

In other words, we do not need the exact sum of calories; knowing the sum modulo \(K\) is sufficient.

Thus, we can define the following DP:

• \(dp[r]\): The number of ways to choose a subset from the sweets processed so far such that the sum of their calories modulo \(K\) is \(r\).

Initially, before choosing any sweets, only the empty set exists, so we set:

\[ dp[0] = 1 \]

This \(1\) represents the “empty set”.

We process the sweets one by one. For each sweet, we transition the DP by considering two choices:

• Do not choose the sweet
• Choose the sweet

Let the calorie of the \(i\)-th sweet modulo \(K\) be:

\[ s = A_i \bmod K \]

For the new sum modulo \(K\) to be \(r\), one of the following must hold:

• The previous sum modulo \(K\) was \(r\), and we do not choose this sweet.
• The previous sum modulo \(K\) was \((r - s) \bmod K\), and we choose this sweet.

Therefore, the transition is:

\[ ndp[r] = dp[r] + dp[(r - s) \bmod K] \]

For example, if \(K = 5\) and \(s = 2\), to make the new remainder \(0\), we can either:

• Start with a remainder of \(0\) and not choose the sweet.
• Start with a remainder of \(3\) and choose the sweet.
  

Indeed, \(3 + 2 \equiv 0 \pmod 5\).

Finally, \(dp[0]\) will store the number of ways to choose a subset whose sum is divisible by \(K\).
However, since this includes the empty set we initialized at the start, the final answer is:

\[ dp[0] - 1 \]

Algorithm

1. Initialize an array \(dp\) of length \(K\).
2. Set \(dp[0] = 1\).
3. For each sweet, calculate \(s = A_i \bmod K\).
4. For each remainder \(r\), perform the following transition:

\[ ndp[r] = dp[r] + dp[(r - s) \bmod K] \]

1. Update \(dp\) with \(ndp\).
2. Finally, print \(dp[0] - 1\).

In this problem, since \(N \times K \leq 2 \times 10^7\), an \(O(NK)\) DP is well within the time limit.

Complexity

• Time Complexity: \(O(NK)\)
• Space Complexity: \(O(K)\)

Implementation Details

When the remainder \(s = 0\), choosing the current sweet does not change the remainder.

In this case, for each state, there are simply two choices (choose or do not choose), so we can just update:

\[ dp[r] \leftarrow 2 \times dp[r] \]

Also, since the answer can be very large, take the modulo \(998244353\) at each step of the calculation.

Finally, to exclude the empty set, print:

\[ dp[0] - 1 \]

Since the subtraction can result in a negative number, adjust it by adding the MOD in that case.

Source Code

#include <bits/stdc++.h>
using namespace std;

static constexpr int MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    vector<int> dp(K, 0), ndp(K, 0);
    dp[0] = 1;

    for (int i = 0; i < N; i++) {
        long long A;
        cin >> A;
        int s = A % K;

        if (s == 0) {
            for (int r = 0; r < K; r++) {
                dp[r] += dp[r];
                if (dp[r] >= MOD) dp[r] -= MOD;
            }
        } else {
            for (int r = 0; r < s; r++) {
                int v = dp[r] + dp[r - s + K];
                if (v >= MOD) v -= MOD;
                ndp[r] = v;
            }
            for (int r = s; r < K; r++) {
                int v = dp[r] + dp[r - s];
                if (v >= MOD) v -= MOD;
                ndp[r] = v;
            }
            dp.swap(ndp);
        }
    }

    int ans = dp[0] - 1;
    if (ans < 0) ans += MOD;
    cout << ans << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-high.