マクロツイーター

はてダから移行した記事の表示が崩れてますが、そのうちに直せればいいのに（えっ）

問題：ナベアツ総和方程式（という名のテスト）

TeX以外

というわけで、早速自分も新しいTeX記法を試してみた。ネタは何でもよかったが、最近ナベアツがにわかに流行っているようなので久しぶりにナベアツしてみた。

問題文

高橋君は、最近にわかにナベアツが流行っていることを知り、特定の範囲にあるナベアツ数の総和に興味を持ちました。ただし「ナベアツ数」とは「3 の倍数または（十進表記で）3 のつく整数」を指します。

与えられた正整数 d に対して、1 から 10^d の範囲にあるナベアツ数の総和を求めてください。

ただし、答えは非常に大きくなる可能性があるので、998244353 で割った余りを出力してください。

制約

  • 1 \leq d \leq 10^5

解説

よく知られているように（えっ🙃）求める総和 S は次の式で求められる。

S = \begin{cases} 18 & \text{（}d = 1~\text{のとき）}\\ \dfrac{(10^d - 1)(81\cdot10^d - 56\cdot9^d)}{162} & \text{（それ以外）} \end{cases}

従って、S を 998244353 で割った余りを求めるプログラムは以下のように書ける。

M = 998244353
for d in range(1, 100001):
    print(
        18 if d == 1
        else (
            (pow(10, d, M) - 1) *
            (81 * pow(10, d, M) - 56 * pow(9, d, M)) *
            pow(162, -1, M) # 逆元
        ) % M
    )

（めでたしめでたし😊）