\(V\) を各値の上限、すなわち \(2 \times 10^5\) とします。

\(M:=M-1\) として、\(B\) を \((0,1,2,\ldots,M)\) の部分列として \(A\) の総和を \(X\)、\(a_i b_i\) の総和を \(Y\) にするものとします。\(N=M+1\)、すなわち \(B=(0,1,2,\ldots,M)\) の場合は、非負整数からなる多重集合であって要素数が \(X\)、総和が \(Y\) で最大値が \(M\) 以下のものを数える問題になります。このときの答えは \(\binom{M+X}{X}_q = \frac{(1-q^{M+X})(1-q^{M+X-1})\ldots(1-q^{M+1})}{(1-q)(1-q^2)\ldots(1-q^X)}\) の \(q^Y\) の係数であることが知られています。

以上を前提として \(N \gt M+1\) の場合を考えます。\(f(K)\) を、非負整数からなる多重集合であって要素数が \(X\)、総和が \(Y\) で最大値が \(M\) 以下かつ含まれる値の種類数が \(K\) であるものの個数とします。すると、答えは \(\sum_{i=1}^{\min(N, K)}\binom{M+1-i}{N-i}f(i)\) です。また、\(1+2+\ldots+n=\frac{n(n+1)}{2}\) であることから \(K\) として考えるべき値の個数は \(\mathrm{O}(\sqrt{V})\) です。\(g(K)\) を非負整数からなる多重集合であって要素数が \(X\)、…かつある \(K\) 個の値が必ず含まれるものの個数として求められると、包除で \(f(K)\) も求められます。

ある \(K\) 個の値が必ず含まれる多重集合は、その \(K\) 個 \(1\) 個ずつと要素数 \(X-K\) の多重集合の組み合わせで作れます。\(K\) 個の値 \(1\) 個ずつは、要素数 \(K\)、最大値が \(M-K+1\) 以下の多重集合に小さい方から \(+0, +1, \ldots, +K-1\) することで得られることから、\(\binom{M+1}{K}_q\) を考えると数えられます。要素数 \(X-K\) の多重集合は \(\binom{X+M-K}{X-K}_q\) となるため、\(g(K)\) は \(h_K=\binom{M+1}{K}_q \binom{X+M-K}{X-K}_q\) の \(q^{Y-\frac{K(K-1)}{2}}\) の係数となります。

\(h_1\) は 形式的べき級数の操作として \(h_1 '=\log h_1\) を考え、\((1-q^i)\) の積を \(\log (1-q^i)\) の和と見なして計算した上で \(\exp(h_1')=h_1\) を求めることで \(\mathrm{O}(Y\log Y)\)で計算できます。また、\(h_2, \ldots,h_K\) を順に求めることにすると差分は定数個の \((1-q^i)\) の乗除のため、\(1\) 回につき \(\mathrm{O}(V)\) で計算できます。 \(K\) の範囲が \(\mathrm{O}(\sqrt{V})\) であることを思い出すと、本問は全体で \(\mathrm{O}(V\sqrt{V})\) で計算できます。