Yêu cầu bài toán: điền các dấu vào các ~a_i~ sao cho tổng ~a_i~ với mọi ~i~ chia hết cho ~k~

Gọi ~dp[i][j]~ : cách điền dấu sao cho tổng ~\sum_{x=1}^{i} a_x~ chia cho ~k~ dư ~j~

TH1: chọn dấu ~+~:

$$ ~dp[i][j] += dp[i - 1][((j - a[i]) \% k + k) \% k~ ~]~ $$

Số cách tạo ra ~\sum_{i=1}^{n} a_i~ chia cho ~k~ dư ~j~ bằng số cách tạo ra ~\sum_{i=1}^{n-1} a_i~ chia ~k~ dư ~x~ với ~x~ ~=~ ~(j - a[i]) \% k~ vì ~x < 0~ ~\Rightarrow~ ~x = ((j - a[i]) \% k + k) \% k~

TH2: chọn dấu ~-~:

$$ ~dp[i][j] += dp[i - 1][(j + a[i]) \% k]~ $$ Tương tự cách tư duy phía trên

by WS team ❤