この問題は関数の合成を扱うモノイド設計をテーマとした問題です。 関数の合成については AtCoder Algorithm Lectures の 区間クエリのためのモノイド設計 第 6 章 にも解説があります。そちらを簡単に引用すると以下の通りです。

• 数列の各要素 \(X_i\) に関数 \(F_{X_i}\) が対応しているとき、
• 列 \(X=(X_0, X_1, \dots, X_{n-1})\) については、\(F_{X_0}, F_{X_1}, \dots, F_{X_{n-1}}\) の合成を \(F_X\) と書き、\(F_X\) を区間情報 \(f(X)\) とします。

列 \(X, Y\) の結合 \(XY\) に対しては、\(F_{XY} = F_Y \circ F_X\) が成り立ちます。したがって、\(\mathrm{op}\) として関数の合成を用いることで、\(\mathrm{op}(f(X), f(Y)) = f(XY)\) を実現できます。

関数の合成は結合法則 \((H \circ G) \circ F = H \circ (G \circ F)\) を満たします。また、恒等関数を単位元とすることで、\(T\) から \(T\) への関数全体は合成についてモノイドとなります。

かいつまんで説明すると関数の合成を \(\mathrm{op}\) として実装できればよいです。

これを踏まえた上で今回の問題を考えてみましょう。今回の問題は、

• \(\mathrm{MOD}(x) = x \bmod 998244353\)
• \(\mathrm{ADD}_a(x) = x + a\)

と置いた時に、この \(2\) 種類の関数を最大 \(N\) 回合成することを考える問題です。
まず、関数の合成を計算する一番シンプルな方法として全ての合成する過程を \(1\) 個 \(1\) 個保持するという方法がありますが、これだと \(N\) 回の合成過程の保持、および \(x\) を代入した時の値の計算に \(\mathrm{O}(N)\) 掛かってしまい実行時間制限を超過してしまいます。そのため、関数の情報を保持する方法に工夫が必要です。

ここで、関数の挙動を観察すると以下の 2 個の事実が分かります。

• 連続する \(\mathrm{ADD}\) 関数は合成できる。
• \(\mathrm{MOD}\) 関数が \(2\) 個以上ある場合、\(1\) 回に減らした等価な表現が可能である。

1 番目については、「\(a\) を足す操作」と「\(b\) を足す操作」は「\(a+b\) を足す操作」にまとめてよいことから従います。数式で説明すると、

\[ \begin{aligned} &(\mathrm{ADD}_b \circ \mathrm{ADD}_a)(x) \\ &= (x+a) + b \\ &= \mathrm{ADD}_{a+b}(x) \end{aligned} \]

となります。
2 番目については、直感的な説明として「最後に剰余を取るタイミングより以前に足したものは全部まとめてよい」という事実から従います。数式で書くと、

\[ \begin{aligned} &(\mathrm{ADD}_c \circ \mathrm{MOD} \circ \mathrm{ADD}_b \circ \mathrm{MOD} \circ \mathrm{ADD}_a)(x) \\ &= ((((x+a) \bmod {998244353}) + b)\bmod{998244353})+c \\ &= ((x+a+b) \bmod {998244353}) + c \\ &= (\mathrm{ADD}_c \circ \mathrm{MOD} \circ \mathrm{ADD}_{a+b})(x) \end{aligned} \]

となります。

ここまでの事実から、

\[G_{a,b} = \mathrm{ADD}_b \circ \mathrm{MOD} \circ \mathrm{ADD}_a\]

と置きます。すると、次の事実が分かります。

• \(\mathrm{MOD}\) と \(\mathrm{ADD}_a\) を自由な順番で複数回合成した関数は、ある整数 \(a\) を用いて \(\mathrm{ADD}_a\) と書けるか、ある整数 \(a,b\) を用いて \(G_{a,b}\) と書くことが出来る。

(証明) \(\mathrm{MOD}\) および恒等関数 \(\mathrm{Id}\) は

\[\mathrm{MOD} = G_{0,0}, \mathrm{Id} = \mathrm{ADD}_0\]

と表すことができる。よって合成する前の関数は条件を満たす。また、\(\mathrm{ADD}\) と \(G\) の合成の組合せ \(4\) 通りについて、

\[\mathrm{ADD}_b \circ \mathrm{ADD}_a = \mathrm{ADD}_{a+b}\]

\[\mathrm{ADD}_c \circ G_{a,b} =G_{a,b+c}\]

\[G_{b,c} \circ \mathrm{ADD}_a =G_{a+b,c}\]

\[G_{c,d} \circ G_{a,b} = G_{a+b+c,d}\]

が成り立つため、合成後も常に条件を満たす。(証明終わり)

よって、関数を \(\mathrm{ADD}_a\) または \(G_{a,b}\) という形で保持することにすれば、関数の合成および代入を \(\mathrm{O}(1)\) で処理することができます。具体的には以下の実装です。

struct S {
  long long A, B;
  bool get_mod;
};

S op(S x, S y) {
  if (y.get_mod) return {(x.A + x.B + y.A) % mod, y.B, true};
  if (x.get_mod) return {x.A, x.B + y.A, true};
  return {x.A + y.A, 0, false};
}

S e() { return {0, 0, false}; }

以上で解説した内容を実装すれば今回の問題を解くことが出来ます。計算量は \(\mathrm{O}(N + Q \log N)\) で十分高速です。

• 実装例, C++