Description:

People in Silverland use coins.They have coins of value A1,A2,A3…An Silverland dollar.One day Tony opened his money-box and found there were some coins.He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn’t know the exact price of the watch.
You are to write a program which reads n,m,A1,A2,A3…An and C1,C2,C3…Cn corresponding to the number of Tony’s coins of value A1,A2,A3…An then calculate how many prices(form 1 to m) Tony can pay use these coins.

Input:

The input contains several test cases. The first line of each test case contains two integers n(1<=n<=100),m(m<=100000).The second line contains 2n integers, denoting A1,A2,A3…An,C1,C2,C3…Cn (1<=Ai<=100000,1<=Ci<=1000). The last test case is followed by two zeros.

Output:

For each test case output the answer on a single line.

Sample Input:

3 10

1 2 4 2 1 1

2 5

1 4 2 1

0 0

Sample Output:

8

4

题目链接

本篇博文以

牛客练习赛22 C 简单瞎搞题(dp+bitset)

为基础。

在“牛客练习赛22 C 简单瞎搞题”中是选择n个区间中选择任意一个数对其平方求和，算种类数，先不看平方就是n个区间中选择任意一个数对其求和，算种类数，当区间长度为1时就和这道题特别像。

可以用一个bitset对每个数进行循环记录求和种类，写法为

for (int i = 0; i < n; ++i) {
	read(c);
	for (int j = 0; j < c; ++j) {
		s |= s << a[i];
	}
}

相当于对每种面值的硬币的每一个都循环计数一次，但是这种写法会超时，需要优化为:

for (int j = 1; j < c; j *= 2) {
	s |= s << (a[i] * j);
	c -= j;
}
s |= s << (a[i] * c);

这么优化的原理是:

以数据

1 10

1 6

为例，在循环中按照原来的写法第一个数需要经过6次循环，其中过程为（取s后10位）:

  • 1100000000（向左移动1位）
  • 1110000000（向左移动2位）
  • 1111000000（向左移动3位）
  • 1111100000（向左移动4位）
  • 1111110000（向左移动5位）
  • 1111111000（向左移动6位）

这样的数据可以解释为若硬币1有六枚则代表这枚硬币的1被记录于s[1~6]，但是移动了六次才记录完成，这里就可以优化:

  • 第一次向左移动一位:1100000000
  • 第二次可以两个一一起向左移动两位，这样第三位上也会被第一位移动后填充1:111100000

循环结束，这时c=2，再向左移动两位即可。因为本来就有n个1整体向左移动n位就会产生2n个1。

最后题目问的是1m之间的种类数，需要在1m中循环遍历统计种类数。

AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <stdlib.h>
#include <deque>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <string>
#include <vector>
#include <bitset>
#include <complex>
#include <functional>
#include <fstream>
#include <ctime>
#include <stdexcept>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
inline void fre() {freopen("in.txt", "r", stdin);/*freopen("out.txt", "w", stdout);*/}

int main() {
//	fre();
	int n, m;
	while (scanf("%d%d", &n, &m), n + m) {
		vector<int> a(n);
		int c;
		bitset<maxn> s;
		s.set(0);
		for (int i = 0; i < n; ++i) {
			read(a[i]);
		}
		for (int i = 0; i < n; ++i) {
			read(c);
			for (int j = 1; j < c; j *= 2) {
				s |= s << (a[i] * j);
				c -= j;
			}
			s |= s << (a[i] * c);
		}
		int ans = 0;
		for (int i = 1; i <= m; ++i) {
			if (s[i]) {
				++ans;
			}
		}
		printf("%d\n", ans);
	}
    return 0;
}