AtCoder ARC020 C

 問題リンク

 https://atcoder.jp/contests/arc020/tasks/arc020_3

 前提となる知識

• \((a + b) \bmod p = (a \bmod p) + (b \bmod p)\)
• \((a * b) \bmod p = (a \bmod p) * (b \bmod p)\)

 解説

 与えられた\(A\)を、文字列をつなげるやり方に代えて掛け算と足し算の繰り返しで構築することを考えます。問題文中の例で考えます。

• はじめに\(A\)を0とする
• \(A\)を1000倍する
• \(A\)に123を足す 
• 123
• \(A\)を1000倍する
• \(A\)に123を足す
• 123123
• \(A\)を10倍する
• \(A\)に4を足す
• 1231234
• \(A\)を10倍する
• \(A\)に4を足す
• 12312344
• \(A\)を100倍する
• \(A\)に56を足す
• 1231234456

 一般的には、次の操作を行えばよいです。

• 変数\(V\)を用意して、これを0とする
• 各\(i\)について、
• 次を\(l_i\)回繰り返す
  
• \(V\)を10の(\(a_i\)の桁数)乗倍する
• \(V\)に\(a_i\)を足す
  

 愚直に計算すると、\(L = \sum_{i=1}^N l_i\)として\(L\)回の操作が必要になり、これは間に合いません。同じ操作を何度も繰り返しているので、これを何とかまとめて計算する方法を考えていきましょう。

 

 例えば繰り返し部分のうち「\(V\)に\(a_i\)を足す」がなければ、\(i\)回目の処理は\(V\)に10を何度か掛け算するだけになります。累乗の計算は、次のようにして高速に行うことができます。

• \(x^{2p} = x^p * x^p\)
• \(x^{2p+1} = x * x^p * x^p\)
  

 指数を半分にしていくことで、\(x^p\)は\(O(\log p)\)で計算できます。

 

 問題のように掛け算と足し算が組み合わさった場合でも、「行列」を使うことで似たようなことができます。\(i\)回目の処理は、\(a_i\)の桁数を\(d_i\)として次のように書けます。

 

\[\begin{pmatrix} nextV \\ 1 \end{pmatrix} = \begin{pmatrix} 10^{d_i} & a_i \\ 0 & 1 \end{pmatrix}^{l_i} \begin{pmatrix} V \\ 1 \end{pmatrix}\]

 \(A\)を求めた後に\(B\)で割ったあまりを求める必要がありますが、愚直に計算すると\(A\)が巨大になるため時間がかかります。途中の積や和を都度\(B\)で割ったあまりにしておくことで、高速に計算できます。

C#のソースコード

using System;

public class Program

{

    public static void Main() => new Program().Solve();

    int p;

    // 行列の掛け算

    long[,] MatrixMultiplication(long[,] m1, long[,] m2)

    {

        var n0 = m1.GetLength(0);

        var n1 = m2.GetLength(1);

        var res = new long[n0, n1];

        for (var i = 0; i < n0; i++) for (var j = 0; j < n1; j++)

        {

            var v = 0L;

            for (var k = 0; k < m1.GetLength(1); k++) v = (v + m1[i, k] * m2[k, j]) % p;

            res[i, j] = v;

        }

        return res;

    }

    // 行列の累乗

    long[,] MatrixPower(long[,] m, long power)

    {

        var n = m.GetLength(0);

        var res = new long[n, n];

        for (var i = 0; i < n; i++) res[i, i] = 1;

        var k = m;

        while (power > 0)

        {

            if (power % 2 == 1) res = MatrixMultiplication(res, k);

            k = MatrixMultiplication(k, k);

            power /= 2;

        }

        return res;

    }

    long Power(long a, long b)

    {

        var res = 1L;

        var k = a;

        while (b > 0)

        {

            if (b % 2 == 1) res = res * k % p;

            k = k * k % p;

            b /= 2;

        }

        return res;

    }

    void Solve()

    {

        string[] input;

        var n = int.Parse(Console.ReadLine());

        var pairs = new (string, string)[n];

        for (var i = 0; i < n; i++)

        {

            input = Console.ReadLine().Split(' ');

            pairs[i] = (input[0], input[1]);

        }

        p = int.Parse(Console.ReadLine());

        var v = new long[2, 1];

        v[1, 0] = 1;

        for (var i = 0; i < n; i++)

        {

            var a = int.Parse(pairs[i].Item1);

            var l = int.Parse(pairs[i].Item2);

            var matrix = new long[2, 2];

            matrix[0, 0] = Power(10, pairs[i].Item1.Length);

            matrix[0, 1] = a;

            matrix[1, 1] = 1;

            v = MatrixMultiplication(MatrixPower(matrix, l), v);

        }

        Console.WriteLine(v[0, 0]);

    }

}