注意：我们需要将dp[0]设置为1，因为如果我们现在需要组成面额为5，然后纸币中又恰有5，那么此时dp[5] = dp[5] + dp[0]。dp[0]=1的意义就是，我现在要组成面额为0，显然只有一种方案，就是不要任何纸币。你有 n 种面额互不相同的纸币，第 i 种纸币的面额为 ai​ 并且有无限张，现在你需要支付 w 的金额，求问有多少种方式可以支付面额 w，答案对 109+7 取模。跟上一个

因为要使最后的异或结果尽可能的大，所以我们考虑每一个数每一位中1出现的次数多还是0出现的次数多。给出一个数组a，长度为n，分别为a1​,a2​,a3​,...an−1​,an​。我们直接用一个二维数组，sum[i][j]，其中i表示第i个数，j表示此数是二进制下从左往右数第j位。对于每次访问，给出一个整数 x(x

对于第二问，我们需要多少个系统，我们即是要求最长上升子序列，因为在这个子序列中，每一个前面的数都不可能和后面的一个数在一个系统中，所以我们需要将每个数都分到不同的系统中。我们维护一个数组len2[i]，表示最长上升子序列长度为i时，结尾的数最小值为len2[i]，我们可以知道len数组时单调递增的。我们维护一个数组len[i]，表示最长不上升子序列长度为i时，结尾的数最大值为len[i]，我们可以

第 3 行有 n−1 个数（0 或 1），表示第一个地窖至第 2 个、第 3 个 …如第 3 行为 11000⋯0，则表示第 1 个地窖至第 2 个地窖有路径，至第 3 个地窖有路径，至第 4 个地窖、第 5 个 …我们定义dp[i]为从i节点出发可以得到的最大地雷数，那么我们可以知道，dp[i] = max(nums[i],nums[i]+dp[j])，其中j大于i。第 n+1 行有 1 个数，

你是一个非常有钱的小朋友。注意： 本题和《进阶篇》的对应题目，输入格式略有差异。你有 n 种面额互不相同的纸币，第 i 种纸币的面额为 ai​ 并且有无限张，现在你需要支付 w 的金额，请问有多少种纸币组合能恰好支付金额 w，答案对 109+7 取模。第一行两个正整数 n,w，分别表示纸币的种数和要凑出的金额。第二行一行 n 个以空格隔开的正整数 a1​,a2​,…an​ 依次表示这 n 种纸币的

每当我们来到一个位置i，我们就对当前区间的范围进行维护，由于我们存入队列中的下标是从小到大的，所以我们队列前面的下标比后面的小，如果当前队列中队首元素比限制区间左端点小，那么我们就将其出队。我们发现，针对每一个位置i，我们都会去搜索i-R到i-L，但我们发现，当i每次往后移动一下时，我们需要遍历的区间也只是往后移动了一下，所以我们只需要维护住i-R到i-L的最大值就可以了，由于每次区间只是往后移动

我们如果需要得目标T最少需要多少张，那么我们可以考虑T-k最少需要多少张（k为已有的纸币的面额），因为这样的话，我们便可直接在此基础上加1得到。某国有 n 种纸币，每种纸币面额为 ai​ 并且有无限张，现在要凑出 w 的金额，试问最少用多少张纸币可以凑出来？由于要求最小数量，所以，我们需要将当前的dp[i]和dp[i-k]（k为目前遍历到的面额）作比较，取最小的即可。对于 100% 的数据，满足

InputOutputExampleinput752 6 8 4 351 4 7 6 942 6 4 10752 1 2 4 252 4 5 4 342 5 5 4outputNOYESYESYESYESNONO。