Long 1 Number

解説

まず最初に思い付くのは、$x$ を求めてから $998244353$ で割る、という方法でしょう。しかし、制約より $K = 10^{18}$ なのでC++などの言語では変数の値は確実にオーバーフローしますし、Pythonのような数値を可変長配列として保持するような言語でも$x$の値の計算に時間がかかってしまいTLEします。 また、$x$ を $1 + 10 + 100 + ...$ のように分解して逐次 $998244353$ で割った値を足していくという方法も考えられますが、こちらも$K$の値が大きいため計算に時間がかかりTLEします。そこで、次のように考えてみます。

$x$ を $1+10+100+...$ のように分解して考えるというところまでは同じです。ここで、$1+10+100+...$ を「初項 $1$ , 公比 $10$ の等比数列の和」として考えると、 $\displaystyle x = \frac{10^K-1}{9}$ となります。ここで、 $10^K$ を $998244353$ で割った余りは繰り返し二乗法を用いて $O(logK)$ で計算できるので、答えとなる $x$ を$998244353$ で割った余りも逆元計算を用いて適切に計算することで時間計算量 $O(logK)$ で計算できます。コンピューターは一秒に $10^6$ 回の計算ができるため、 本制約においては余裕を持って実行時間制限に間に合います。 よって、この問題を解くことができました。