이진 부분수열
시간 제한1초메모리 제한512 MB
K가 최대 10^6일 때 서로 다른 비어 있지 않은 부분수열을 정확히 K개 가지는 이진 문자열의 개수를 1e9+7로 나눈 나머지로 세고, 그런 문자열 중 가장 짧은 것을 출력한다.
문제
과학 위원회는 큰 곤경에 빠졌다. 좋은 문제는 떠올렸지만, 그 문제의 테스트 데이터를 만들 수 있을지 확신이 없기 때문이다. 문제 지문은 이렇다.
"0과 1로만 이루어진 문자열이 주어질 때, 그 문자열에 나타나는 서로 다른 비어 있지 않은 부분수열의 개수를 구하라."
여기서 문자열의 부분수열이란, 처음 문자열에서 몇 개의 문자를 지워서(하나도 지우지 않아도 된다) 얻을 수 있는 문자열을 말한다. 두 부분수열은 길이가 다르거나 적어도 한 위치에서 다르면 서로 다른 것으로 본다. 예를 들어 문자열 "101"에는 서로 다른 비어 있지 않은 부분수열이 6개 있다. "0", "1", "10", "01", "101", "11"이다.
위원회는 물론 테스트를 무작위로 생성하고 공식 소스로 각 테스트의 답을 계산할 수도 있지만, 이 방식은 출제자를 만족시키지 못한다. 출제자는 출력을 완전히 통제하고 싶어 한다. 주어진 파일의 각 값 K에 대해, 서로 다른 비어 있지 않은 부분수열을 정확히 K개 가지는 이진 문자열이 몇 개인지, 그리고 그러한 문자열 중 가장 짧은 것은 무엇인지 알고 싶어 한다. 조건을 만족하는 문자열이 여러 개라면 그중 아무거나 답으로 인정한다. 첫 번째 질문의 답은 매우 클 수 있으므로 1,000,000,007로 나눈 나머지만 알고 싶어 한다.
입력
입력의 첫 줄에는 뒤따르는 K 값의 개수 T가 주어진다. 다음 T개 줄에는 문제에서 설명한 두 질의에 답해야 하는 K 값이 주어진다.
출력
입력 파일의 각 K 값에 대해 2줄을 출력한다.
첫 줄에는 서로 다른 비어 있지 않은 부분수열을 정확히 K개 가지는 이진 문자열의 개수를 1,000,000,007로 나눈 나머지를 출력하거나, 이 질의를 건너뛰려면 -1을 출력한다. -1이 아닌 수를 출력하면 질문에 답하려 한 것으로 간주한다.
둘째 줄에는 질의를 건너뛰려면 -1을 출력한다. 그렇지 않으면 공백으로 구분된 L개의 이진 숫자를 출력한다. 이 숫자들은 서로 다른 비어 있지 않은 부분수열을 정확히 K개 가지는 최소 길이 이진 문자열 중 하나를 이루어야 한다.
제한
- T ≤ 10
- K ≤ 1,000,000
힌트
K = 2일 때, 서로 다른 비어 있지 않은 부분수열을 2개 가지는 문자열은 정확히 2개다. "00"(부분수열 "0", "00")과 "11"(부분수열 "1", "11")이다. 문자열 "11"도 길이가 최소이므로 채점기에서 정답으로 인정된다.
K = 3일 때, 조건을 만족하는 문자열은 4개다. "10"(부분수열 "0", "1", "10"), "01"(부분수열 "0", "1", "01"), "000"(부분수열 "0", "00", "000"), "111"(부분수열 "1", "11", "111")이다.
K = 8일 때 첫 번째 질의를 건너뛰었고, "1100"은 서로 다른 비어 있지 않은 부분수열을 정확히 8개 가진다. "0", "00", "1", "11", "110", "1100", "10", "100"이다.