【AtCoder】ABC 357 D - 88888888 | 茶コーダーが解くAtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 970

問題概要

正整数 $N$ に対して、 $N$ を $N$ 個つなげた整数を $V_N$ とする。 $V_N$ を $998244353$ で割った余りを出力せよ。

制約

$N$ は整数。
$1 \leq N \leq 10^{18}$

考察

$10^{18}$ を $10^{18}$ 回もつなげた数を扱えるわけもないので、何か工夫が必要。ここで、 $N$ の桁数を $l$ として、いったん $V_N$ を式で表してみると、
$\begin{align*} V_N & = 10^{0}N + 10^{l}N + 10^{2l}N + \cdots + 10^{(N-1)l}N \\ & = N \displaystyle \sum_{i=0}^{N-1}10^{il} \\ & = N \cdot \dfrac{10^{Nl} - 1}{10^l - 1} \\ \end{align*}$
のように、等比数列の和の形になる。

これを $\mod 998244353$ すると、積はそのまま積の形で良いが、商については逆元をとるという、少々特殊な方法を取らなければならない。詳しくはこちらの記事を参照のこと。

qiita.com

式で表すとこんな感じ。 $x^{-1}$ は、 $\mod 998244353$ における $x$ の逆元を表している。
$\begin{align*} V_N & \equiv N \cdot \dfrac{10^{Nl} - 1}{10^l - 1} \\ & \equiv N \cdot (10^{Nl} - 1) \cdot (10^l - 1)^{-1} \pmod {998244353} \end{align*}$

$\textrm{mod}$ 演算における累乗や逆元の計算は実装が少々面倒くさいが、それを解決するのが AC Library のmodintである。詳しくはこちら。

これを使うことで、各演算を1行で行うことができ実装も簡単になる。

ただし、一つ注意したいのが、 $10^{Nl} - 1$ の $10^{Nl}$ の計算だ。mint(10).pow(Nl)としてしまうと、 $N \times l$ の計算でオーバーフローしてしまうためうまくいかない。mint(10).pow(l).pow(N)のように、ひとつずつ計算していくこと。

コード

#include <bits/stdc++.h>
#include <atcoder/modint>

using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;

// ======================================== //

int main()
{
    ll N;
    cin >> N;

    string N_str = to_string(N);
    ll l = N_str.length();

    mint p = mint(10).pow(l).pow(N) - 1;

    mint q = mint(10).pow(l) - 1;
    mint q_inv = q.inv();

    mint result = p * q_inv * N;

    cout << result.val() << endl;

    return 0;
}