17239번 - Linear-Feedback Shift Register

LFSR(Linear-Feedback Shift Register)에 대해서 알고 있는가? LFSR는 의사 난수 값을 생성하는 데 쓰이기도 한다. 이에 대해서 자세히 공부하는 것은 생략하도록 하고, 대신 문제에서는 수식으로 간단하게 정의를 하고자 한다. 문제의 LFSR은 36-bit LFSR이다.

초기값 r₀ ∼ r₃₅(r_i = 0 or 1)와, 다음 Output이 어떤 값들의 XOR로 이루어지는지 정의하는 값 a₀ ∼ a₃₅(a_i = 0 or 1)로 정의된다. LFSR의 Output들은 r₃₆ 부터의 r 값들이다. r₃₆ 이후의 r 값들은 다음과 같이 정의된다: (k는 0 이상의 정수)

r_k+36 = (a₃₅ · r_k+35) ⊗ (a₃₄ · r_k+34) ⊗ ... ⊗ (a₀ · r_k)

(Bitwise AND는 ·, Bitwise XOR은 ⊗로 표기했다.)

이 문제에서 묻고 싶은 것은 a₀ ∼ a₃₅이 주어져 있을 때 N개의 Output들, 즉 r₃₆부터 r_35+N 까지의 값들을 보고 이를 만족하는 초기값 r₀ ∼ r₃₅이 있는지 답하는 것이다.

첫 번째 줄에 a₀ ∼ a₃₅가 띄어쓰기를 사이에 두고 주어진다.

두 번째 줄에 입력으로 들어올 Output의 개수 N(1 ≤ N ≤ 64)이 주어진다.

세 번째 줄에 r₃₆ ∼ r_35+N 이 띄어쓰기를 사이에 두고 주어진다.

첫 번째 줄에 가능한 r₀ ∼ r₃₅가 존재하는지의 여부를 YES 혹은 NO로 출력한다. YES라면 두 번째 줄에 가능한 r₀ ∼ r₃₅ 조합 중 r₀r₁r₂...r₃₅가 사전순으로 가장 빠른 조합을 r₀, r₁, ... , r₃₅ 순서대로 띄어쓰기를 사이에 두고 출력한다. 000...000이 가장 사전 순으로 빠르며, 111...111이 가장 사전 순으로 느리다.

첫 번째 예제는 r₃₆ = r₃₅ ⊗ r₃₄ ⊗ r₃₃ = 1, r₃₇ = r₃₆ ⊗ r₃₅ ⊗ r₃₄ = 0, r₃₈ = r₃₇ ⊗ r₃₆ ⊗ r₃₅ = 1로 풀어서 쓸 수 있다. 이를 만족하는 r₃₃, r₃₄, r₃₅는 0, 1, 0 뿐이다. r₀ ∼r₃₂은 어떠한 값이 와도 상관 없다. 그러나 이 중 사전순으로 가장 빠르려면 r₀, r₁, ... , r₃₂ = 0이여야 한다.

두 번째 예제는 모든 a_i 값이 0이기 때문에 가능한 Output은 0뿐이다. 그러나 1이 왔으므로 답은 NO이다.