K-문자열

시간 제한1초메모리 제한1024 MB

요약

길이가 10인 숫자 문자열 N개가 주어질 때, 이어 붙인 문자열의 서로 다른 숫자 개수가 정확히 K개인 쌍 i<j의 개수를 구한다.

난이도: 보통10점 중 6점
유형: 비트 연산, 해시맵, 조합론, 완전 탐색
정답자: 아직 제출이 없습니다

문제

서로 다른 문자의 개수가 $K$ 개인 문자열을 K-문자열이라고 하자.

길이가 $10$ 이고 숫자로만 이루어진 문자열 $N$ 개가 주어진다. 두 문자열 $s\_i,s\_j\left(1 \le i\<j \le N \right)$ 을 이어 붙였을 때 K-문자열이 될 수 있는 순서쌍 $\left( i,j \right)$ 의 개수를 구해보자. 입력으로 주어지는 문자열과 이어 붙인 문자열은 $0$ 으로 시작할 수 있다.

입력

첫째 줄에 문자열의 개수 $N$ 과 $K$ 가 공백으로 구분되어 주어진다. $\left( 2\le N\le 1\\, 000\\, 000;\ 1\le K\le 10 \right)$

둘째 줄부터 $N$ 개의 줄에 걸쳐 $i+1$ 번째 줄에 길이가 $10$ 인 문자열 $s\_i$ 가 주어진다.

출력

K-문자열이 되는 $i\<j$ 를 만족하는 순서쌍 $\left( i,j \right)$ 의 개수를 출력한다.

힌트

입출력의 양이 많으므로, 빠른 입출력을 사용하는 것을 권장합니다. 대표적인 언어에 따른 빠른 입출력은 아래를 참고하세요.

C++: cin, cout을 사용하는 경우 입출력 전에 cin.tie(nullptr); ios::sync_with_stdio(false);를 한 번 적용해야 합니다. 줄 바꿈할 때는 endl 대신 '\n'을 사용해야 합니다.
Java: BufferedReader와 BufferedWriter를 사용해야 합니다.
Python3, PyPy3: input() 대신 sys.stdin.readline().rstrip()을 사용해야 합니다.

예제2

예제 1

입력

예상 출력

예제 2
입력
```
2 2
0101010101
1010101010
```
예상 출력
```
1
```