BOJ 28261 - 화이트, 다크, 민트 초콜릿

BOJ 28261 - 화이트, 다크, 민트 초콜릿

각 문자를 $0,1,2$로 표현하자.

어떤 두 문자가 합쳐져 나오는 수를 $f(x,y)$라고 한다면 $f(x,y)=-(x+y) \pmod 3$ 이다.

가장 낮은 곳에 $x$ 가 있고 그 수가 위로 가면서 어떻게 영향을 미치나 보자.

처음엔 $x$이다.

위로 한칸 가면 $-x, -x$ 가 된다.

위로 한칸 더 가면 $x, 2x, x$ 처럼 된다.

마치 파스칼의 삼각형처럼 수가 늘어나고 그럼 $k$번을 올라가면 $(-1)^{k} \cdot 2^{k}$ 가 기여되는게 아닌가? 싶을 수 있다.

그러나 이건 위로 뾰족한 삼각형이기 때문에 저 수만큼 기여할 수 있지 않다.

$i$에서 가장 위칸까지 가는 경로의 개수를 생각한다. 그럼 위 칸까지 $n-1$ 번 이동해야 하는데, 왼쪽으로 $i$번, 오른쪽으로 $n-1-i$ 번 이동하는 경우의 수임을 알 수 있고, 결국 이 경로의 가지수가 $a_i=x$ 가 가장 위 꼭지점에 기여하는 $x$ 의 개수임을 알 수 있다.

따라서 $a_i=x$ 라면 $(-1)^{n-1} \cdot \dbinom{n-1}{i}x \pmod 3$ 만큼 정답에 기여가 된다.

이항 계수를 전처리한다음 쿼리도 쉽게 처리해줄 수 있다.

팩토리얼을 이용해서 쿼리를 날려놓거나 뤼카 정리를 이용해 풀 수도 있다.

코드

int bino[4][4];  
int bino_mod[500001];  
  
void solve() {  
   for (int i = 0; i <= 3; i++)  
      for (int j = 0; j <= i; j++)  
         bino[i][j] = !i || !j ? 1 : md(3, bino[i - 1][j] + bino[i - 1][j - 1]);  
  
   int n;  
   cin >> n;  
  
   for (int k = 0; k <= n - 1; k++) {  
      int N = n - 1, K = k;  
      bino_mod[k] = 1;  
      while (N || K) {  
         bino_mod[k] *= bino[N % 3][K % 3];  
         bino_mod[k] %= 3;  
         N /= 3, K /= 3;  
      }  
   }  
  
   string s;  
   cin >> s;  
   vi a(n);  
   auto idx = [&](char c) {  
      return c == 'W' ? 0 : c == 'D' ? 1 : 2;  
   };  
   auto ch = [&](int i) {  
      return i == 0 ? 'W' : i == 1 ? 'D' : 'M';  
   };  
   for (int i = 0; i < n; i++) a[i] = idx(s[i]);  
   int q;  
   cin >> q;  
  
   int ans = 0;  
  
   auto val = [&](int i) {  
      return md(3, bino_mod[i] * a[i] * ((n - 1) % 2 ? -1 : 1));  
   };  
  
   for (int i = 0; i < n; i++) ans = md(3, ans + val(i));  
  
   cout << ch(ans) << endl;  
   while (q--) {  
      int i;  
      string c;  
      cin >> i >> c, i--;  
  
      ans -= val(i);  
      a[i] = idx(c[0]);  
      ans = md(3, ans + val(i));  
  
      cout << ch(ans) << endl;  
   }  
}