합으로 나오는 짝의 수
다이아몬드 V의견: 0
두 정수 다중집합 \(A = \{a_1, \dots, a_n\}\)과 \(B = \{b_1, \dots, b_m\}\)이 주어진다. 모든 원소는 \(0\) 이상 \(V\) 이하의 정수이다.
\(Q\)개의 질의가 주어진다. 각 질의는 정수 \(t\)로 이루어지며, \(a + b = t\)를 만족하는 순서쌍 \((a, b)\) (\(a \in A,\ b \in B\), 같은 값의 원소는 출현 횟수만큼 구별)의 개수를 \(998{,}244{,}353\)으로 나눈 나머지를 출력해야 한다.
각 질의마다 모든 쌍을 세면 너무 느리다.
\(1 \le n, m \le 200{,}000\)
\(1 \le V \le 200{,}000\)
\(0 \le a_i, b_j \le V\)
\(1 \le Q \le 200{,}000\)
\(0 \le t_k \le 2V\)
첫째 줄에 \(n\), \(m\), \(V\)가 주어진다.
둘째 줄에 \(A\)의 원소 \(a_1, \dots, a_n\)이 공백으로 구분되어 주어진다.
셋째 줄에 \(B\)의 원소 \(b_1, \dots, b_m\)이 공백으로 구분되어 주어진다.
넷째 줄에 질의 수 \(Q\)가 주어진다.
다섯째 줄에 \(Q\)개의 질의 값 \(t_1, \dots, t_Q\)가 공백으로 구분되어 주어진다.
각 질의에 대해 \(a + b = t\)인 순서쌍의 개수를 \(998{,}244{,}353\)으로 나눈 나머지를 한 줄에 하나씩 출력한다.
3 2 2
1 2 2
0 2
4
2 3 4 0
2
1
2
0\(A=\{1,2,2\}\), \(B=\{0,2\}\). 합이 2인 쌍: \((2,0),(2,0)\) 그리고 \((1,?)\)는 없음 → 2개. 합이 3: \((1,2)\) → 1개. 합이 4: \((2,2),(2,2)\) → 2개. 합이 0: 없음 → 0개.
1 1 1
0
0
3
0 1 2
1
0
0\(A=\{0\}\), \(B=\{0\}\). 유일한 쌍 \((0,0)\)의 합은 0. 따라서 합 0은 1개, 합 1과 2는 0개이다.
riseoj 작성
출처 Original
평가 및 의견
합으로 나오는 짝의 수
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
합으로 나오는 짝의 수