Overview

Given \(N\) shops, Takahashi selects \(P\) shops and Aoki selects \(Q\) shops (without overlap), and each decides an amount within the allowed range at their respective shops. The problem asks to find the total number of plans where both persons’ total amounts are equal, after each update.

Analysis

Key Insight

• The condition “Takahashi’s total = Aoki’s total” can be rephrased as “Takahashi’s total − Aoki’s total = 0”.
• For each shop, there are 3 choices: “skip”, “Takahashi uses it (difference increases)”, or “Aoki uses it (difference decreases)”, so the problem can be solved by tracking the difference with DP.

Range of the Difference

• Takahashi uses at most \(P\) shops with at most \(20\) yen each, so the maximum difference is \(P \times 20 = 60\)
• Aoki uses at most \(Q\) shops with at most \(20\) yen each, so the minimum difference is \(-Q \times 20 = -60\)
• The range of the difference is \([-60, 60]\), which is at most \(121\) possible values.

Utilizing the Constraints

Given the constraint \(N \times M \leq 2000\), we can afford to recompute the DP from scratch for each query.

Algorithm

After each query, execute the following DP.

State: \(\mathrm{dp}[p][q][d]\) = the number of ways such that, after considering the first several shops, Takahashi has shopped at \(p\) shops, Aoki has shopped at \(q\) shops, and (Takahashi’s total) − (Aoki’s total) = \(d - \mathrm{DOFF}\).

Initial state: \(\mathrm{dp}[0][0][\mathrm{DOFF}] = 1\) (difference \(0\), no one has shopped yet)

Transitions: For shop \(i\) (range \([L_i, R_i]\)): 1. Skip: \(\mathrm{ndp}[p][q][d] \mathrel{+}= \mathrm{dp}[p][q][d]\) 2. Takahashi purchases (when \(p < P\)): For amount \(a \in [L_i, R_i]\), \(\mathrm{ndp}[p+1][q][d+a] \mathrel{+}= \mathrm{dp}[p][q][d]\) 3. Aoki purchases (when \(q < Q\)): For amount \(a \in [L_i, R_i]\), \(\mathrm{ndp}[p][q+1][d-a] \mathrel{+}= \mathrm{dp}[p][q][d]\)

Answer: \(\mathrm{dp}[P][Q][\mathrm{DOFF}]\) after processing all shops (difference is exactly \(0\))

Complexity

• Time complexity: \(O(N \times M \times P \times Q \times D \times V)\)
  • \(D = 121\) (number of difference states), \(V = 20\) (maximum range of amounts per shop)
  • Since \(N \times M \leq 2000\) and \(P, Q \leq 3\), the total is approximately \(2000 \times 9 \times 121 \times 20 \approx 4.4 \times 10^7\)
• Space complexity: \(O(P \times Q \times D)\) (two layers of DP table)

Implementation Notes

• Since the difference can be negative, we add an offset \(\mathrm{DOFF} = 60\) to make array indices non-negative. \(\mathrm{DSIZE} = 121\) corresponds to the \(121\) values in \([-60, 60]\).

• Cells with DP value \(0\) are skipped to improve the constant factor.

• To prevent out-of-bounds array access, checks such as \(d + a < \mathrm{DSIZE}\) and \(d - a \geq 0\) are included.

• For each query, the DP table is initialized with memset and recomputed from scratch (sufficiently fast given the constraint \(N \times M \leq 2000\)).

  Source Code

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

const int MOD = 998244353;
const int DOFF = 60;
const int DSIZE = 121;

long long dp[4][4][DSIZE];
long long ndp[4][4][DSIZE];

int main(){
    int N, P, Q, M;
    scanf("%d %d %d %d", &N, &P, &Q, &M);
    
    vector<int> L(N), R(N);
    for(int i = 0; i < N; i++){
        scanf("%d %d", &L[i], &R[i]);
    }
    
    for(int query = 0; query < M; query++){
        int x, a, b;
        scanf("%d %d %d", &x, &a, &b);
        x--;
        L[x] = a;
        R[x] = b;
        
        memset(dp, 0, sizeof(dp));
        dp[0][0][DOFF] = 1;
        
        for(int i = 0; i < N; i++){
            memset(ndp, 0, sizeof(ndp));
            int li = L[i], ri = R[i];
            
            for(int p = 0; p <= P; p++){
                for(int q = 0; q <= Q; q++){
                    for(int d = 0; d < DSIZE; d++){
                        if(dp[p][q][d] == 0) continue;
                        long long val = dp[p][q][d];
                        
                        // Skip
                        ndp[p][q][d] = (ndp[p][q][d] + val) % MOD;
                        
                        // Takahashi buys
                        if(p < P){
                            for(int am = li; am <= ri; am++){
                                int nd = d + am;
                                if(nd < DSIZE){
                                    ndp[p+1][q][nd] = (ndp[p+1][q][nd] + val) % MOD;
                                }
                            }
                        }
                        
                        // Aoki buys
                        if(q < Q){
                            for(int am = li; am <= ri; am++){
                                int nd = d - am;
                                if(nd >= 0){
                                    ndp[p][q+1][nd] = (ndp[p][q+1][nd] + val) % MOD;
                                }
                            }
                        }
                    }
                }
            }
            
            memcpy(dp, ndp, sizeof(dp));
        }
        
        printf("%lld\n", dp[P][Q][DOFF] % MOD);
    }
    
    return 0;
}

---

This editorial was generated by claude4.6opus-thinking.