더 좋게, 더 빠르게!

머리가 깨질 듯한 두통과 함께 잠에서 깨어나니, 상사가 시켰던 프로그램에 대한 흐릿한 기억만 남아 있습니다. 로그인하니 어제 작성해 둔 핵심 함수가 보입니다.

unsigned int checksum (char str[], int len) {
    unsigned int r = 0;
    for (int k=0; k<8*len; k++) {               // iterate over the bits of str
        if ((r & (1<<31)) != 0) r = (r << 1) ^ 0x04c11db7;
                           else r = (r << 1);   // do some magic
        if (str[k/8] & 1<<(7-k%8))              // if the k-th bit of str is set,
            r ^= 1;                             // flip the last bit of r
    }
    return r;
}

주석은 잘 달아 두었지만 "do some magic" 부분은 여전히 이해하기가 조금 어렵습니다. 그래도 함수 이름이 checksum인 만큼, 이 함수는 주어진 문자열을 한 비트씩 처리하며 일종의 체크섬을 계산합니다.

원래 과제는 주어진 문자열에 대해 이 체크섬을 계산하고, 이어서 문자열을 조금씩 수정한 여러 버전에 대해서도 계산하는 것이었습니다. 프로그램의 나머지 부분도 그럴듯해 보입니다.

#include <stdio.h>

int main() {
    char str[1000001],c;
    int TESTS,n,changes,p;
    for (scanf ("%d", &TESTS); TESTS>0; TESTS--) {
        scanf ("%d %s", &n, str);               // read the input
        printf ("%u\n", checksum(str, n));      // checksum of the original string
        for (scanf ("%d", &changes); changes>0; changes--) {
            scanf ("%d %c", &p, &c);            // apply the change
            str[p-1] = c;
            printf ("%u\n", checksum(str, n));  // checksum of the modified string
        }
    }
}

이 프로그램은 정확하지만 너무 느리므로, 훨씬 더 빠르게 동작하도록 만들어야 합니다. (힌트에 있는 동등한 자바 버전은 어찌 된 일인지 더 느리게 동작합니다.)

입력은 여러 개의 테스트 케이스로 이루어집니다. 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 양의 정수 $Z \le 20$이 주어집니다. 이어서 $Z$개의 테스트 케이스가 주어집니다.

여기서 문자 란 하나의 소문자, 대문자, 또는 숫자를 뜻합니다.

각 테스트 케이스의 첫 번째 줄에는 자연수 $n$ ($1 \le n \le 10^6$)과 문자열 $s$가 공백 하나로 구분되어 주어집니다. $s$는 정확히 $n$개의 문자로 이루어집니다. 다음 줄에는 $s$에 적용할 변경의 횟수 $t$ ($0 \le t \le 10^5$)가 주어집니다. 이어지는 $t$개의 줄에는 각각 자연수 $p \in [1, n]$과 문자 $c$가 공백 하나로 구분되어 주어지며, 이는 $s$의 $p$번째 문자를 $c$로 바꾼다는 의미입니다.

위 프로그램이 출력하는 것과 동일한 결과를 출력하세요. 즉, 각 줄에 체크섬을 하나씩, 총 $t + 1$개의 줄을 출력합니다. 첫 번째 체크섬은 원래 문자열 $s$에 대해 계산한 값이고, 나머지 체크섬들은 각 변경을 $s$에 적용한 뒤에 계산한 값입니다.

프로그램의 동등한 자바 버전 (이 버전은 더 느리게 동작합니다):

import java.util.Scanner;

public class Compute {

    static long checksum (byte[] str, int len) {
        int r = 0;
        for (int k=0; k<8*len; k++) {                  // iterate over the bits of str
            if ((r & (1<<31)) != 0) r = (r << 1) ^ 0x04c11db7;
            else r = (r << 1);                         // do some magic
            if ((str[k/8] & 1<<(7-k%8)) != 0)          // if the k-th bit of str is set,
                r ^= 1;                                // flip the last bit of r
        }
        long rr = (r<0 ? r+0x100000000L : r);          // Java has no unsigned int
        return rr;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        for (int TESTS = in.nextInt(); TESTS>0; TESTS--) {
            int n = in.nextInt();                      // read the input
            byte[] str = in.next().getBytes();         // checksum of the
            System.out.println (checksum(str,n));      // original string
            for (int changes = in.nextInt(); changes>0; changes--) {
                int p = in.nextInt();                  // apply the change
                byte c = in.next().getBytes()[0];
                str[p-1] = c;
                System.out.println (checksum(str,n));  // checksum of the
            } // modified string
        }
    }
}