AtCoder Beginner Contest 448, E : Simple Division

問題文

　https://atcoder.jp/contests/abc448/tasks/abc448_e

問題概要

　非負整数 $n$, 正整数 $m $ が与えられるので，$\left\lfloor \frac n m \right\rfloor \bmod 10{,}007$ を求めよ．
　ただし，$n$ は Run Length Encoding された形で与えられる（詳細は原文参照）．

制約

• $1 \leq m \leq 10^4$
• $\text{$n$ の桁数} \leq 10^{ 13 }$

解法

　剰余の定義を思い出すと，非負整数 $a$ と正整数 $b$ について $a = qb + r$ ($0 \leq r < b$) が成り立つとき，$q$ を商 (quotient)，$r$ を剰余 (remainder) と呼ぶのでした．また，$q = \left\lfloor \frac a b \right\rfloor$ です．
　上記を用いて定義で問題を言い換えると，非負整数 $q$ 正整数 $r$
\[
n = qm + r
\]
満たすとき，$q$ を $10{,}007$ で割った余りを求める問題と言えます．これを言い換えると非負整数 $q'$，正整数 $r'$ ($0 \leq r' < 10{,}007$) を使って
\[
q = 10{,}007 q' + r'
\]
として，$r'$ が問題の答えです．これを先程の式の $q$ に代入すると
\begin{align*}
n &= ( 10{,}007 q' + r' ) m + r \\
\left\lfloor \frac n m \right\rfloor &= ( 10{,}007 q' + r' ) m
\end{align*}
を得ます．右辺を展開すると
\[
10{,}007 q' m + r' m
\]
で，欲しい値を $10{,}007 m $ を法として表すと $r' m$ であると解釈できるので，$\left\lfloor \frac { r' } m \right\rfloor$ が答えとなります．
　値の計算方法ですが，整数 $x$ の最下位桁に $y$ を挿入するケースはよく見かけて，更新後の値は $10x + y$ となります．しかし，今回の制約で $1$ 桁ずつ追加していると間に合わないので高速化が必要です．複数桁をまとめて挿入する方法を考えると，$x$ の最下位桁に $d$ 桁の $y$ を挿入するときは $x \times 10^d + \text{$y$ を $d$ 個並べた数}$ になります．$\text{$d$ を $y$ 個並べた数}$ の計算を各 $d$ について別々にやると TLE しますが，ダブリングによる高速化が可能です．
\[
dp[y][k] = \text{$y$ を $2^k$ 個並べた値の $10{,}007 m$ での剰余}
\]
を各 $y, k$ について前計算しておいて，反復二乗法のような気持ちで必要な分を挿入していくことで高速に処理できます．

コード

#include <atcoder/modint>
using namespace atcoder;

using MINT = modint;

int main()
{
	IN( int, K, M );
	VI C( K ), L( K );
	REP( i, K )
	{
		cin >> C[i] >> L[i];
	}

	MINT::set_mod( 10'007 * M );

	VVT< MINT > dp( 10, VT< MINT >( 31 ) );
	REP( i, 10 )
	{
		dp[i][0] = i;
		REP( j, 30 )
		{
			dp[i][ j + 1 ] = dp[i][j] * MINT( 10 ).pow( 1 << j ) + dp[i][j];
		}
	}

	MINT res = 0;
	REP( i, K )
	{
		REP( j, 30 )
		{
			if ( L[i] & 1 << j )
			{
				res *= MINT( 10 ).pow( 1 << j );
				res += dp[ C[i] ][j];
			}
		}
	}

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

	return 0;