Alternative Fast Fourier Transform solution
Intuition\nWe can use the Fast Fourier Transform (FFT) to determine the number of multisets having sum $k$ for all $k$ simultaneously by encoding the Knapsack p
# Intuition\nWe can use the [Fast Fourier Transform (FFT)](https://en.wikipedia.org/wiki/Fast_Fourier_transform) to determine the number of multisets having sum $k$ for all $k$ simultaneously by encoding the Knapsack problem as one of polynomial multiplication.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSuppose the (deduped) entries of `nums` are $k_1, k_2, \\ldots, k_s$ with occurrences $v_1, v_2, \\ldots, v_s$. Then, consider the polynomial $$f(x) = \\prod_{i=1}^{s}\\left(\\sum_{j=0}^{v_i} x^{k_i\\cdot j}\\right)$$. We claim that the coefficient of $x^i$ in this polynomial is exactly the number of ways to form a multiset summing to $i$: indeed, this comes from expanding the polynomial.\n\nTo actually compute this polynomial, we use the Fast Fourier Transform, which when applied to two polynomials of degree $a$ and $b$ takes time $O((a + b)\\log(a + b))$ to compute their product. To make sure we don\'t accidentally multiply the highest degree polynomial over and over, we use the [Huffman Coding](https://en.wikipedia.org/wiki/Huffman_coding#Compression) priority queue idea to multiply the two polynomials of smallest degree at each iteration. Since the total degree of the final polynomial $f(x)$ is $m$, this takes time $O(m\\log^2 m)$ (it\'s possible this bound is too loose). To simulate the priority queue, we need $O(n\\log n)$ time giving the full bound.\n\n# Complexity\n- Time complexity:\nLet $m$ be the sum of all entries. Then, the runtime is $O(n\\log n + m\\log^2 m)$.\n\n- Space complexity:\nThe space complexity is $O(m + n)$.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nusing ll = long long;\nusing ld = long double;\nusing pii = pair<int, int>;\nusing vi = vector<int>;\n#define rep(i, a, b) for(int i = a; i < (b); ++i)\n#define all(x) begin(x), end(x)\n#define sz(x) (int)(x).size()\n#define smx(a, b) a = max(a, b);\n#define smn(a, b) a = min(a, b);\n#define pb push_back\n#define endl \'\\n\'\n\nconst ll MOD = 1e9 + 7;\n\ntypedef complex<double> C;\ntypedef vector<double> vd;\nvoid fft(vector<C>& a) {\n\tint n = sz(a), L = 31 - __builtin_clz(n);\n\tstatic vector<complex<long double>> R(2, 1);\n\tstatic vector<C> rt(2, 1);  // (^ 10% faster if double)\n\tfor (static int k = 2; k < n; k *= 2) {\n\t\tR.resize(n); rt.resize(n);\n\t\tauto x = polar(1.0L, acos(-1.0L) / k);\n\t\trep(i,k,2*k) rt[i] = R[i] = i&1 ? R[i/2] * x : R[i/2];\n\t}\n\tvi rev(n);\n\trep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;\n\trep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);\n\tfor (int k = 1; k < n; k *= 2)\n\t\tfor (int i = 0; i < n; i += 2 * k) rep(j,0,k) {\n\t\t\t// C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled)  /// include-line\n\t\t\tauto x = (double *)&rt[j+k], y = (double *)&a[i+j+k];        /// exclude-line\n\t\t\tC z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]);           /// exclude-line\n\t\t\ta[i + j + k] = a[i + j] - z;\n\t\t\ta[i + j] += z;\n\t\t}\n}\n\ntypedef vector<ll> vl;\ntemplate<int M> vl convMod(const vl &a, const vl &b) {\n\tif (a.empty() || b.empty()) return {};\n\tvl res(sz(a) + sz(b) - 1);\n\tint B=32-__builtin_clz(sz(res)), n=1<<B, cut=int(sqrt(M));\n\tvector<C> L(n), R(n), outs(n), outl(n);\n\trep(i,0,sz(a)) L[i] = C((int)a[i] / cut, (int)a[i] % cut);\n\trep(i,0,sz(b)) R[i] = C((int)b[i] / cut, (int)b[i] % cut);\n\tfft(L), fft(R);\n\trep(i,0,n) {\n\t\tint j = -i & (n - 1);\n\t\toutl[j] = (L[i] + conj(L[j])) * R[i] / (2.0 * n);\n\t\touts[j] = (L[i] - conj(L[j])) * R[i] / (2.0 * n) / 1i;\n\t}\n\tfft(outl), fft(outs);\n\trep(i,0,sz(res)) {\n\t\tll av = ll(real(outl[i])+.5), cv = ll(imag(outs[i])+.5);\n\t\tll bv = ll(imag(outl[i])+.5) + ll(real(outs[i])+.5);\n\t\tres[i] = ((av % M * cut + bv) % M * cut + cv) % M;\n\t}\n\treturn res;\n}\n\nclass Solution {\npublic:\n    int countSubMultisets(vector<int>& nums, int l, int r) {\n        map<int, int> occ;\n        for (auto x : nums) {\n            occ[x]++;\n        }\n        vector<vector<ll>> polys;\n        for (auto [k, v] : occ) {\n            vector<ll> poly(k * v + 1);\n            for (int r = 0; r <= v; r++) {\n                poly[k * r]++;\n            }\n            polys.push_back(poly);\n        }\n\n        priority_queue<pii, vector<pii>, greater<>> pq;\n        for (int i = 0; i < polys.size(); i++) {\n            pq.push({polys[i].size(), i});\n        }\n        while (pq.size() > 1) {\n            auto [d1, i1] = pq.top(); pq.pop();\n            auto [d2, i2] = pq.top(); pq.pop();\n            pq.push({d1 + d2 - 1, polys.size()});\n            polys.push_back(convMod<MOD>(polys[i1], polys[i2]));\n        }\n\n        ll ans = 0;\n\n        for (int i = l; i <= min(r, sz(polys.back()) - 1); i++) {\n            ans = (ans + polys.back()[i]) % MOD;\n        }\n\n        return ans;\n    }\n};\n```
['C++']