問題一覧 > 通常問題

No.3553 Good Quartet

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 32
作問者 : ぽえ / テスター : ルク 👑 loop0919 mitani lif4635 hiro1729
お気に入りにしたユーザー ProblemId : 13329 / 自分の提出
問題文最終更新日: 2026-11-04 02:05:29
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もしくは右上の雲マークをクリックしてアカウントを作成してください。