六年级学生，CSP-J在即，求各位大佬提点建议！

给你一个长度为 $n$ 的序列 $a$，值域很大。$q$ 次询问，每次询问给你一个 $k$，问你长度为 $k$ 的子序列的 $a_i$ 的和有多少种。要求 $O(n)$ 或 $O(n\log n)$。