No.3553 Good Quartet
問題文最終更新日: 2026-11-04 02:05:29
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
yukicoder contest 500
(順位表)
の他の問題:
Problem Statement
A set $A = \{a_1, a_2, a_3, a_4\}$ of $4$ positive integers is defined to be a good set if it satisfies the following condition.
- Among the pairs of integers $(i, j)$ with $1 \le i < j \le 4$, there are exactly $\bm{\color{red}{4}}$ pairs such that $a_1+a_2+a_3+a_4$ is a multiple of $ a_i+a_j$.
You are given a set $S = \{s_1, s_2, \dots, s_N\}$ of $N$ positive integers.
You are given $Q$ queries. The $q$-th query is given as a pair of integers $(t_q, x_q)$, and its content is as follows.
- If $t_q = 1$: add $x_q$ to $S$.
- If $t_q = 2$: remove $x_q$ from $S$.
After processing each query, find the number, modulo $998244353$, of subsets of $S$ that are good sets.
Constraints
- All input values are integers.
- $1 \le N, Q \le 2\times 10^5$
- $1 \le s_i \le 10^9$ $(1 \le i \le N)$
- $s_i \neq s_j$ $(1 \le i < j \le N)$
- $t_q \in \{1, 2\}$ $(1 \le q \le Q)$
- $1 \le x_q \le 10^9$
- When $t_q = 1$, it is guaranteed that $x_q \notin S$ immediately before the query.
- When $t_q = 2$, it is guaranteed that $x_q \in S$ immediately before the query.
Input
The input is given from standard input in the following format.
$N$ $Q$ $s_1$ $s_2$ $\dots$ $s_N$ $t_1$ $x_1$ $t_2$ $x_2$ $\vdots$ $t_Q$ $x_Q$
Output
Print $Q$ lines. On the $q$-th line, print the number, modulo $998244353$, of subsets of $S$ that are good sets, immediately after processing the $q$-th query.
Sample
Sample 1
Input
20 7 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 23 2 20 1 21 2 5 1 22 2 19 1 5
Output
1 1 1 0 1 1 2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
ぽえ
mitani