まず、等差数列の要素の桁数が決まっているものとします。なぜ決まっているものとするかというと、「等差数列の要素は全て$10^{18}$未満」という制約があるからです。この制約により、等差数列の全ての要素を左から右に順番に並べたときに、以下のことが言えます。
つまり、もし桁数が決まっているときの解を高速に求めることができれば、それを高々$18$回行うだけで、最終的な答えが得られます。ということで、桁数が決まっている場合について考察します。
初項$x$、公差$y$、要素の桁数を$k$とおきます。まずは$3$番目の要素の解がどのような式で表せるかを手元で試してみます。すると次のような式になります。
\[A_3 = x(10^{2k} + 10^k + 1) + y(0 \cdot 10^{2k} + 1 \cdot 10^k + 2 \cdot 1)\]一般化すると、$N$番目の要素の解は次の式になります。
\[A_N = x(10^{(N-1) \cdot k} + \ldots + 10^{0 \cdot k}) + y(0 \cdot 10^{(N-1)k} + \ldots + (N - 1) \cdot 10^{0 \cdot k})\]見通しを良くするために$ \sum $を導入して$T = 10^k$とおきます。最終的には次の式になります。
\[A_N = x \sum_{i=0}^{N-1} T^i + y \sum_{i=0}^{N-1} (i \cdot T^{N - 1 - i})\]つまり、$\sum T^i$と$\sum (i \cdot T^{N - 1 - i})$を高速に求めることができれば、$A_N$を高速に求めることができます。ということで、これらをどのようにして高速に求めるかについて考えます。
$g(N) = \sum T^i$、$h(N) = \sum (i \cdot T^{N - 1 - i})$とおきます。$g(N)$は等比数列の和の公式を使って、$h(N)$は等比数列と等差数列の和の求め方を使って求められます。しかし、これらの式は割り算を含んでいます。
今回の問題では、最終的に$M$で割った余りを求めたいので、途中の計算をmod $M$を取りながら進めていくことになります。しかし、もし$M$が素数でないなら、「割り算を含む計算」を行うことは簡単ではありません。
よって、割り算を使わずに$g(N)$と$h(N)$を求めたいです。そこで次のことを考えます。
もし$g(N)$から$g(N+1)$と$g(N \times 2)$を求めることができれば、$N$が巨大な整数であっても高速に答えを求めることができます。たとえば$N = 10,000$のときは、計$17$回の再帰で済みます。
$g(N)$から$g(N + 1)$を求めるのは簡単で、$g(N + 1) = g(N) + T^N$とすればよいです。$g(N)$から$g(N \times 2)$を求める方法ですが、一度手元で$g(2)$と$g(4)$の式を書いてみて、どのようにして$g(2)$の式から$g(4)$の式にできるかを考えるという方法があります（このあたりを上手くやる方法はよくわかりません…）。
この方法で、$g(N \times 2) = g(N) \times (T^N + 1)$という式が立てられます。あとは$g(1)$のときの値を定義すれば終わりです。これは自明で、$g(1) = 1$です。
同じ方法で、$h(N)$のときの漸化式を立てます。最終的には次のような式になります。
これで、$g(N)$と$h(N)$を高速で求められるようになりました。よって$A_N$も高速で求めることができ、この問題を解くことができました。計算量は$O(c \log^3N)$（$c$は桁数の種類数）です。
$f(N + 1)$と$f(N \times 2)$の漸化式を立てるという方法は、解説放送で使われていた方法です。この方法を使うことで、「等比数列の和の公式」を知らなくても等比数列の和を求めることができます。ということで、競プロの面白さを再認識した問題でした。