うし数列 2 [yukicoder No.793]

https://yukicoder.me/problems/no/793

解説

https://yukicoder.me/submissions/319055

桁ごとに分解して考えると、例えば、1333は
1333 = 1000 + 300 + 30 + 3
となる。
つまり、10^N + (3 + 30 + ... + 3*10^(N-1))である。
10^Nは繰り返し二乗法で高速に計算でき、後半は等比数列の総和なので、公式を使えば高速に計算可能。
mod上での計算なのでmintを使うことをすすめるが、pythonを使ってもいい。

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    mint ans = mint(10)^N;
    ans += touhism(mint(3), mint(10), N);
    cout << ans << endl;
}