U142789 【1123T2】ZZH与背包

【原题空间限制2048MB】

有 $n$ 个物品，第 $i$ 个物品的体积为 $v[i]$。 $q$ 次查询，每次给出 $l,r$，求选出物品子集的方案数、使得集合中物品的总体积在 $[l,r]$ 范围内。

第一行2个整数 $n,q$ 第二行 $n$ 个整数 $v[1...n]$ 接下来 $q$ 行，每行2个整数 $l,r$ 代表一组询问

输出 $q$ 行，每行1个整数代表答案

对于所有数据，保证 $1\le n\le 40, q\le 500, 1\le v[i]\le 10^9, 1\le l\le r\le \sum v[i]$。 对于测试点1，$q=0$ 对于测试点2-5，$n\le 20$ 对于测试点6-8，$n\le 25$ 对于测试点9-11，$q=1$ 对于测试点12-16，$n\le 32$ 对于测试点17-20，无特殊限制