小課題

頂点 \(0,1,\dots,N-1\) を用意して、 \(x=0,1,\dots,N-1\) と \(a \in A\) に対して\(x\) から \(x-a\) や \(x+a\) に辺を貼ったグラフを考えると、\(f(x)\) は頂点 \(0\) から頂点 \(x\) への最短路の長さに等しいので、BFSなどのアルゴリズムにより、 \(f(0),f(1),\dots,f(N-1)\) を \(O(NM)\) で求めることができます。

満点

\(O(\frac{N^2}{w}+M)\) 解法

まだ見ていない点の集合をbitsetで持っておきます。小課題のBFSをするときに、ある頂点 \(x\) からたどり着ける点の集合は、bitsetで \(A<<x\) のように表せるため、これとまだ見ていない点のandを取ることにより、\(x\) から移動できる点（この点の個数を \(k_x\) とすると）を \(O(\frac{N}{w}(1+k_x))\) などで列挙することができます。 \(\sum_{x=0}^{N-1}k_x=N-1\) なので、全体の計算量は \(O(\frac{N^2}{w})\) になります。

\(O(N(logN)^2+M)\)解法

\(B_i\) が負でもいいのはめんどくさいので、\(A\) に \((-a)%N\) （\(a \in A\)）も追加しておきます。 ここから重複を許して \(c\) 個選んで足し合わせたときに \(i=0,1,\cdots,N-1\) について \(i(modN)\) になるかを計算します。\(f=1+\sum_{a \in A} x^a\) とすると、 \(f^c(mod(1-x^N))\) の \(x^i\) の項が \(0\) でないこと（\(i=0,1,\dots,N-1\)）が条件で、これはFFTで高速化できます。普通に二分探索+繰り返し二乗法をしてしまうと \(O(N(logN)^3)\) になりますが、二分探索の仕方をビットの上の桁から決めていく形式で（上のビットから見るダブリングのような感じで）計算していけば、 \(O(N(logN)^2)\) になります。 \(f^c\) の係数は \(0\) かどうかが重要なので、二乗をして \(2\) 以上になったらその都度 \(1\) にするといった処理をすれば衝突が防げて確定的に解くことができます。 \(f^c\) を \(mod998244353\) のまま計算する解法は落ちるケースを入れてあります。このケースはmaspyさんに作っていただきました。ありがとうございます。