[19499] K-transform

 거꾸로 생각합시다. k-transform으로 만들어지는 수는 $k(k(k(...(k(1+a_0)+a_1)...+a_{n-1})+a_n$의 꼴($0\le a_n<k,a_0\ne k-1$)이고, 여기서 $\sum _{i=0}^n{a}_i+n=m$이 됩니다. 저걸 전개해버리면 $(1+a_0)k^n+a_1{k}^{n-1}+...+a_{n-1}k+a_n$입니다. 이걸 $k$진 수로 생각하면 $(1+a_0)a_1{a}_2{a}_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\mathrm{mod}k$인 경우는 모든 $\text{digit sum}=s$인 $k$진 수에 각각 $k$를 곱해서 만들 수 있고,

$N\equiv 1\mathrm{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\mathrm{mod}k$인 경우는 모든 $x=s-1$인 $k$진 수에 $k$를 곱해서 만들 수 있습니다. $N\equiv 1\mathrm{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