ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#8064

양말 1s 1024MB

問題

정올이는 2X개의 양말을 가지고 있다.

1번째 ~ X번째 양말은 왼발에 신을 수 있는 양말이고, X+1번째 ~ 2X번째 양말은 오른발에 신을 수 있는 양말이다.

양말의 색은 총 K가지 존재하고, 각각 1번 색, 2번 색, \cdots, K번 색이라고 부른다.

i번째 양말의 색은 A_i번 색이다.

정올이는 왼발 양말 하나와 오른발 양말 하나를 신고 나가려 한다. 양쪽 발에 신는 양말의 색은 달라야 한다. 정올이가 이와 같이 양말을 신고 가는 경우의 수는?


入力

첫째 줄에 양말의 개수 X와 양말의 색의 가짓수 K가 공백을 사이에 두고 주어진다.

둘째 줄에 각 양말의 색의 번호를 나타나는 2X개의 수 A_1, A_2, \cdots, A_{2X}가 공백을 사이에 두고 주어진다.

[제약 조건]

  • 1 \le X \le 100\,000

  • 1 \le K \le 10\,000

  • 1 \le A_i \le K (1 \le i \le 2X)


出力

양쪽 발에 신는 양말의 색이 다르도록 정올이가 양말을 신고 가는 경우의 수를 출력하라. 답의 크기가 32비트 정수형의 범위를 초과할 수 있음에 유의하라.


例題 #1

4 5
1 3 2 4 3 1 1 5
13

정올이는 왼발 전용 양말을 총 4개 가지고 있으며, 각 양말의 색은 1, 3, 2, 4번 색이다.

정올이는 오른발 전용 양말을 총 4개 가지고 있으며, 각 양말의 색은 3, 1, 1, 5번 색이다.

정올이가 양쪽 발에 양말을 신고 가는 경우는, (왼발 양말의 색, 오른발 양말의 색) = (1, 3), (1, 5), (3, 1), (3, 1), (3, 5), (2, 3), (2, 1), (2, 1), (2, 5), (4, 3), (4, 1), (4, 1), (4, 5)인 총 13가지 경우가 있다.


例題 #2

5 3
1 1 1 1 1 3 3 3 3 3
25

例題 #3

5 3
2 2 2 2 2 2 2 2 2 2
0


出典

연세대학교 미래캠퍼스 강원도 대학생 코딩 경진대회 B번
ログインしないとコードを書けません。