# Less than K の別解について

まずはこれを読もう
https://twitter.com/nuo_chocorusk/status/1359028664290037764?s=20

\
ここでは鏡像法パートについてだけもう少しかみ砕いて解説します

要するに、操作ごとに $x^az^b(|a|>K)$ の項を無視するという境界条件を暗に考慮したいので、 $x,z$ の次数を軸にした二次元グリッドを考え $i=K+1,-K-1$ を境界面に設定します

ここで、初期値を $(0,0)=1$ の他に $(2K+2,-2K-2)=-1$ を追加し $i,j$ を $\bmod 4K+4$ で同一視することで、境界条件を考慮することができます

\
お気持ち：遷移は、一辺が $4K+4$ の正方形を $(0,+1),(-1,+1),(0,-1),(+1,-1)$ の４方向へ移動するのと対応している(上、左上、下、右下)　ただし、上下左右の端は繋がっているものとする ($\bmod 4K+4$ なので)

$(0,0)$ にある駒が上の遷移を繰り返すとき、 $(2K+2,-2K-2)$ にある駒が $(0,+1),(+1,-1),(0,-1),(-1,+1)$ という移動を同時に行うことで、図のように鏡映された世界を考える
(薄赤,薄青は各々の初期値を表している　赤い軸は境界面を表し、値は常に $0$ となる)


よって、境界面に乗るような移動は鏡映された駒によって相殺され、無かったものとして扱うことができる

\
あとは、言い換えた係数をいい感じに計算してやればよいです(投げやり)