くるのプログラミング記録

プログラミングの感想とか解説とか。

OUPC2020 C. Symmetric NBase Number 解説

[謝罪]
問題文のサンプルの表現が間違っていました。すみません。
正しくは f(41,-4) = (1, 2, 3) です。






{\displaystyle a}の{\displaystyle b}進数表現、{\displaystyle -b}進数表現について考えると、数列{\displaystyle c=(c_0, \cdots ,c_N)}と数列{\displaystyle d=(d_0,\cdots,d_M)}を用いて下記のように書けます。

{\displaystyle a = c_0 + c_1*b + c_2*b^2 + c_3*b^3 + ...... + c_N*b^N}
{\displaystyle a = d_0 - d_1*b + d_2*b^2 - d_3*b^3 + ...... + (-1)^M*d_M*b^M}

ただし{\displaystyle c_i,d_i}はいずれも{\displaystyle b}より小さい非負整数
{\displaystyle f(a,b)}と{\displaystyle f(a,-b)}が一致するという条件は、数列{\displaystyle c}と{\displaystyle d}が一致するということと同値です。 このとき{\displaystyle N=M}が必要となり、下記の式が成り立ちます。

{\displaystyle c_0=d_0}
{\displaystyle c_1=d_1}
{\displaystyle \vdots }
{\displaystyle c_N=d_N}
ここで、どちらの数も{\displaystyle a}であるので

{\displaystyle c_0 + c_1*b + c_2*b^2 + c_3*b^3 + ...... + c_N*b^N = d_0 - d_1*b + d_2*b^2 - d_3*b^3 + ...... + (-1)^N*d_N*b^N}
{\displaystyle \Leftrightarrow}
{\displaystyle c_0 + c_1*b + c_2*b^2 + c_3*b^3 + ...... + c_N*b^N = c_0 - c_1*b + c_2*b^2 - c_3*b^3 + ...... + (-1)^N*c_N*b^N}

すなわち下記の条件が成り立ちます
{\displaystyle c_1*b + c_3*b^3 + ...... + c_{2L-1}*b^{(2L-1)} = 0}
ここで{\displaystyle 2L-1}は{\displaystyle N}以下の最大の奇正数です。

上記式が恒等的に成り立つことと、{\displaystyle b > 1}であることを考慮すると

{\displaystyle c_{2i-1} = 0}
が題意を満たす条件です。

すなわち{\displaystyle b}進数変換した際の、奇数桁が{\displaystyle 0}であるような{\displaystyle (a,b)}の組の数え上げに言い換えることが出来ます。
これは{\displaystyle b}を決め打ちし、そのあとは桁dpを行うことで求めることが出来ます。
よって計算量{\displaystyle O(B \log A)}でこの問題を解くことが出来ました。