[19499] K-transform

 거꾸로 생각합시다. k-transform으로 만들어지는 수는 $k(k(k(...(k(1+a_0)+a_1)...+a_{n-1}) + a_n$의 꼴($0 \leq a_n < k, a_0 \neq k-1$)이고, 여기서 $\sum_{i=0}^na_i + n = m$이 됩니다. 저걸 전개해버리면 $(1+a_0)k^n + a_1k^{n-1} + ... + a_{n-1}k + a_n$입니다. 이걸 $k$진 수로 생각하면 $(1+a_0)a_1a_2a_3...a_{n-1}a_{n\ (k)}$, 그러니까 $\text{digit sum} + \text{digit}-1 = m$인 모든 $k$진 수의 개수를 구하는 문제가 됩니다.

 

 쉽지 않네요... 그렇죠? 애초에 제약 없이 수를 나누는 문제도 중복조합으로 풀어야 하는데... 제약이 더 걸려있으니 까다롭지요.

 대단한 공식은 구해 봐야 시간 내에 계산할 수 없는 꼴일 가능성이 높고, 음... 어떻게 하면 좋을까요.

어떤 $k$진 수 $N$의 첫번째 자리 수, 그러니까 $N \text{ mod } k$가 $0$인 경우, $1$인 경우, $2$인 경우... $k-1$인 경우로 나눠 봅시다. 이 때 $N$의 $\text{digit sum}$이 $s$라면:

$N \equiv 0 \mod{k}$인 경우는 모든 $\text{digit sum} = s$인 $k$진 수에 각각 $k$를 곱해서 만들 수 있고,

$N \equiv 1 \mod{k}$인 경우는 모든 $\text{digit sum} = s-1$인 $k$진 수에 각각 $k$를 곱한 뒤 $1$을 더해서 만들 수 있고

...

 그렇게 생각하면 $\text{digit sum} = s, s-1, ..., s-k$인 모든 경우를 다 더해서 $\text{digit sum} = s$인 경우를 만들 수 있습니다.

 그런데 이건 원래 구하려고 했던 게 아니잖아요? 자릿수도 고려대상에 넣어야 하잖아요? $k$를 곱한다는 것은 연산을 하나 소모하는 거고... 그럴 거면 애초에 $\text{digit sum}$이 아니고 $\text{digit sum} + \text{digit} - 1$(앞으로 $x$로 줄여 부를게요)을 가지고 뭘 해야겠죠.

 

 또 다시 어떤 $k$진 수 $N$의 $\text{mod }k$ 값을 가지고 경우를 나눠 봅시다. $N \equiv 0 \mod{k}$인 경우는 모든 $x = s - 1$인 $k$진 수에 $k$를 곱해서 만들 수 있습니다. $N\equiv 1 \mod{k}$는 $x=s-2$인 경우에 $k$ 곱하고 $1$ 더해서... 그렇게 $k-1$을 더하는 경우까지 가면 $x$가 $s-1$부터 $s-k$인 경우까지 쭉 더하면 $x=s$인 모든 경우의 수가 나온다는 걸 알 수 있습니다. 보기 편하게 정리할까요.

 $k$는 그냥 상수로 두고, $C_s$를 $x = s$인 모든 $k$진 수의 개수라고 합시다. 그럼 $C_s = C_{s-1}+ ... + C_{s-k}$가 됩니다.

 이전 $k$개의 항으로 결정되는 선형 점화식을 얻었습니다. 이제 키타마사법을 적용하면 $C_{m}$의 값을 $O(k^2\log{m})$에 구할 수 있습니다. 시간 초과도 받을 수 있습니다. $K^2$는 너무 큽니다.

 

 키타마사를 돌릴 적에, 다항식 나눗셈에 대한 추가적인 최적화가 가능합니다. 이게 점화식의 계수가 다 같아서 할 수 있는 짓인데, 다항식 $C_k - \sum_{i=0}^{k-1} C_{i}$으로 다른 다항식을 나눌 때를 잘 관찰해 보면 연속적인 구간에 다 같은 값을 더하는 짓을 반복합니다. 여기에 레이지 세그를 먹이면 $K \log K$에 다항식 나머지를 구하는 짓이 가능해집니다.

 

 근데 $C_{0}$ ~ $C_{k-1}$을 구해야 키타마사를 돌리겠죠? 저건 잘 모르겠으니 냅다 나열해봅시다. 우선 편의상 $k$가 충분히 큰 임의의 자연수라고 합시다. 한 100이면 괜찮을까요.

$C_0 = 1$입니다. $1$이 있습니다.

$C_1 = 2$입니다. $k, 2$가 있습니다.

$C_2 = 4$입니다. $k^2, k+1, 2k, 3$이 있습니다.

$C_3 = 8$입니다. $k^3, k^2+1, 2k^2, k(k+1), k+2, 2k+1, 3k, 4$이 있습니다.

 

 딱 감이 오죠? 이거 $C_n = 2^n\ (n < k - 1)$입니다. 애초에 모든 경우에서 두 갈래로($\times k$, $+1$) 뻗어나갈 수 있는데 최종 겹치는 경우는 하나도 없으니깐 성립합니다. 그러다가 1에서 $+1$로만 뻗은 가지가 $k$를 건드리면 끝납니다.

 $C_{k-1}$은 1에서 $+1$로만 뻗은 녀석이 $k$에 다다르기 때문에 그 경우만 빼 주면 되어서 $2^{k-1}-1$입니다. 와~

 

 아무래도 정해는 Bostan-Mori 알고리즘인 것 같습니다. 언젠가 읽어봐야겠습니다.

19499번: K-transform