BOJ 10370 - Ball

BOJ 10370 - Ball

BOJ 28261 와 비슷한 이항계수 조합론 문제이다.

$W=0, R=1, G=2$ 로 나타내면 한 턴이 지난 후에 $f(x,y)=(x+y) \pmod 3$ 이 된다.

이 꼴이 이항계수처럼 나오는데,

한 턴이 지나면 $i$ 번째 자리가 $a_i+a_{i+1}$이 되고,

두턴이 지나면 $a_i+2a_{i+1}+a_{i+2}$가 되고 세턴이 지나면

$a_i+3a_{i+1}+3a_{i+2}+a_{i+3}$ 이 된다.

그런데 우린 $3$으로 나눈 나머지가 필요하므로 $a_i+a_{i+3}$이 된다.

이항계수 $\dbinom{n}{k}$에서 $n$이 $3$의 거듭제곱 수일 때, 항상 $\dbinom{n}{0}=\dbinom{n}{n}=1$ 을 제외하고 모두 $3$의 배수이다.

$\because$ $\dbinom{n}{k}=\dfrac{n(n-1) \cdots (n-k+1)}{k!}$ 여서 항상 $n$에 $3$이 하나이상 남기 때문이다. 분모에서 $3$의 거듭제곱 지수가 분자에있는 것보다 이상이 될 수 없다.

따라서 $n \ge 3^k$ 인 $k$를 계속 골라가며 $a_i \coloneqq a_i+a_{i+3^k} \pmod 3$ 을 진행하고 $n$에서 $3^k$ 를 빼는것을 반복한다.

이 횟수는 $O(\log_3 n)$ 이 걸리고 문제를 $O(T \cdot \vert S \vert \cdot \log_3 N)$ 에 해결할 수 있다.

const ll mod = 3;  
inline ll md(ll x) { return md(mod, x); }  
int idx(char c) {  
   return c == 'W' ? 0 : c == 'R' ? 1 : 2;  
}  
char ch(int i) {  
   return i == 0 ? 'W' : i == 1 ? 'R' : 'G';  
}  
void solve() {  
   string s;  
   cin >> s;  
   int m = sz(s), n;  
   cin >> n;  
  
   vi cnt(3);  
   int k = 1;  
   while (k * 3 <= n) k *= 3;  
   vi a(m);  
   for (int i = 0; i < m; i++) a[i] = idx(s[i]);  
   while (n) {  
      int q = n / k;  
      while (q--) {  
         vi b = a;  
         for (int i = 0; i < m; i++) {  
            b[i] = (a[i] + a[md(m, i + k)]) % 3;  
         }  
         a = b;  
         n -= k;  
      }  
      k /= 3;  
   }  
   for (int i = 0; i < m; i++) cnt[a[i]]++;  
   for (int i: cnt) cout << i << ' ';  
   cout << endl;  
  
}