AtCoder Beginner Contest 353, D : Another Sigma Problem

問題文

　https://atcoder.jp/contests/abc353/tasks/abc353_d

問題概要

　関数 $f_s( x )$ を，整数 $x$ を $x$ を $10$ 進数で表現する文字列に変換する関数とし，関数 $f_i( S )$ を，正整数を $10$ 進数で表現する文字列 $S$ を $S$ が表現する正整数に変換する関数とする．また，文字列に対する二項演算 $\mathord{+}$ を文字列の連結として定義する．
　$n$ 項からなる正整数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ が与えられる．式
\begin{equation*}
\sum_{ i = 1 }^{ n - 1 }\sum_{ j = i + 1 }^{ n } f_i( f_s( A_i ) + f_s( A_j ) )
\end{equation*}
を $998{,}244{,}353$ で割った余りを求めよ．

制約

• $2 \leq n \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$

解法

　制約から $\Omega( n^2 )$ 時間はかけられないので，工夫する必要があります．
　$A_i, A_j$ を文字列化して連結するという操作の特性上，$A_i$ による和への寄与は，$A_j$ の桁数によって変わってしまい，扱いづらそうです．対して，$A_j$ の方を固定すると関係する $A_i$ は一様に $A_j$ の桁数分「シフト」されます．具体的には，$A_j$ の桁数を $d$ として，各 $A_i$ は $A_i \times 10^d$ だけ和に寄与します．よって，$j$ の方を先に固定する方が計算しやすそうです．
　「しやすそう」というか，各 $j$ に対して $A_1, A_2, \dots A_{ j - 1 }$ がすべて $10^d$ 倍されるので，そこまでの和だけ覚えておけば計算できてしまいます．$A_j$ による寄与は単純に，関係する $A_i$ の個数分だけ足されます．よって，各時点までに見た値の和を保持しながら $A$ を走査し，各 $A_j$ の桁数を求めて算数をすれば答えが求まります．
　計算量としては各 $j$ に対して桁数を求めるのにかかる時間を考慮する必要があるので，全体で $O( n \log( \max A ) )$ 時間となります．

コード

main = getLine >> readInts >>= print . solve 0 . zip [ 0 .. ]

m = 998244353

infixl 6 +%
a +% b = ( a + b ) `mod` m

infixl 7 *%
a *% b = ( a * b ) `mod` m

solve _ [] = 0
solve s ((i,a):rest) = s *% pow10 +% a *% i +% solve ( s +% a ) rest
	where
	l = length $ show $ a
	pow10 = 10^l `mod` m

#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;

int main()
{
	IN( int, N );
	VLL A( N );
	cin >> A;

	mint res = 0, sum = 0;
	REP( i, N )
	{
		const int L = SZ( toString( A[i] ) );

		LL pow10 = 1;
		REP( L )
		{
			pow10 *= 10;
		}

		res += sum * pow10;
		res += A[i] * i;
		sum += A[i];
	}

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

	return 0;
}