Transport Ship （二进制优化多重背包）

Transport Ship （二进制优化多重背包）

There are NN different kinds of transport ships on the port. The i^{th}ith kind of ship can carry the weight of V[i]V[i] and the number of the i^{th}ith kind of ship is 2^{C[i]} - 12C[i]−1. How many different schemes there are if you want to use these ships to transport cargo with a total weight of SS?

It is required that each ship must be full-filled. Two schemes are considered to be the same if they use the same kinds of ships and the same number for each kind.

Input

The first line contains an integer T(1 \le T \le 20)T(1≤T≤20), which is the number of test cases.

For each test case:

The first line contains two integers: N(1 \le N \le 20), Q(1 \le Q \le 10000)N(1≤N≤20),Q(1≤Q≤10000), representing the number of kinds of ships and the number of queries.

For the next NN lines, each line contains two integers: V[i](1 \le V[i] \le 20), C[i](1 \le C[i] \le 20)V[i](1≤V[i]≤20),C[i](1≤C[i]≤20), representing the weight the i^{th}ith kind of ship can carry, and the number of the i^{th}ith kind of ship is 2^{C[i]} - 12C[i]−1.

For the next QQ lines, each line contains a single integer: S(1 \le S \le 10000)S(1≤S≤10000), representing the queried weight.

Output

For each query, output one line containing a single integer which represents the number of schemes for arranging ships. Since the answer may be very large, output the answer modulo 10000000071000000007.

样例输入

11 22 112

样例输出

01

题目大概：

有n种船，每种船可以装vi重量的货物，这种船有ci艘。有q次询问，每次询问s重量的货物，恰好运送完的方案数。

思路：

多重背包方案数的问题，但是每种船的数量有点多，直接转化01背包会超时。

用二进制优化，把ci艘的i船的分为多个不同的物品，每个物品包含2^0，2^1，2^2...艘i种船。减少物品种类，这样再用01背包会好很多，每种物品的数量都会加一个log。

代码：

#include using namespace std;#define ll long longconst int maxn=1e4+100;const int mod=1e9+7;ll v[100],c[100];ll dp[maxn];ll lis[2001];int main(){ int t; scanf("%d",&t); while(t--) { int n,q; scanf("%d%d",&n,&q); memset(lis,0,sizeof(lis)); for(int i=1;i<=n;i++) { scanf("%lld%lld",&v[i],&c[i]); } int ans=0; for(int i=1;i<=n;i++) { ll sum=(1<=lis[i];k--) { dp[k]=(dp[k]+dp[k-lis[i]])%mod; } } while(q--) { int x; scanf("%d",&x); printf("%lld\n",dp[x]); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。