BOJ 31294 Convolution

문제 링크:

문제 내용

길이 $2^n$의 배열 $f$와 $g$가 주어집니다. 다음의 식으로 정의되는 배열 $h$를 구하세요. 식에서 $j | k$는 $j$와 $k$의 bitwise OR를 의미합니다.

입력

첫 줄에는 $n$의 값과 테스트 케이스의 개수 $t$가 주어집니다. ($1 \le n \le 16$, $1 \le t \le 100$)

그 다음 줄에는 각 테스트 케이스를 생성할 파라미터 값 $a$와 $b$가 주어집니다. ($1 \le a, b \le 10^9$)

$a$와 $b$의 값을 이용하는 PRNG 함수 rand16을 다음과 같이 정의합시다.

state = 0
def rand16():
    global state
    state = (state * a + b) % (2 ** 32)
    return state >> 16

그러면 각각의 테스트 케이스에 대해, 먼저 rand16을 $2^n$번 호출하여 순서대로 배열 $f$의 원소를 얻고, 그 다음 rand16을 $2^n$번 호출하여 순서대로 배열 $g$의 원소를 얻어야 합니다. state는 테스트 케이스 사이에 초기화되지 않습니다.

출력

각 테스트 케이스에 대해, $(\sum_{i = 0}{2^n-1} h(i) \times (i+1)) \bmod 2^{32}$를 출력합니다.

문제 풀이