牛牛的背包问题

Map.prototype.floorKey = function(key) {
	let map = this;
	let ans = null;
	for(let k of map.keys()) {
		if(k > key) {
			break;
		} else {
			ans = k;
		}
	}
	return ans;
}
// 根据数据量描述，2^30>10^8，采用分而治之的思路
function ways(arr, bag) {
	let len = arr.length;
	if(arr == null || len == 0) {
		return 0;
	}
	if(len == 1) {
		return arr[0] <= bag ? 2: 1;
	}
	let mid = (len - 1) >> 1;
	let lmap = new Map();
	let ways = process(arr, 0, 0, mid, bag, lmap);
	let rmap = new Map();
	ways += process(arr, mid + 1, 0, len - 1, bag, rmap);
	// 对rmap进行手动排序，以模拟TreeMap，这里先不用手动实现有序表，太冗长
	rmap = new Map([...rmap.entries()].sort((a, b) => a[0] - b[0]));
	let rpre = new Map();
	let pre = 0;
	for(let [key, value] of rmap.entries()) {
		pre += value;
		rpre.set(key, pre); // 方法前缀和map
	}
	for(let [lweight, lways] of lmap.entries()) {
		let floor = rpre.floorKey(bag - lweight);
		if(floor != null) {
			let rways = rpre.get(floor);
			ways += lways * rways;
		}
	}
	return ways + 1; // process中没考虑都不选的情况，所以方法加1
}
function process(arr, index, w, end, bag, map) {
	if(w > bag) {
		return 0;
	}
	if(index > end) {
		if(w != 0) {
			if(!map.has(w)) {
				map.set(w, 1);
			} else {
				map.set(w, map.get(w) + 1);
			}
			return 1;
		} else {
			return 0;
		}
	} else {
		let ways = process(arr, index + 1, w, end, bag, map);
		ways += process(arr, index + 1, w + arr[index], end, bag, map);
		return ways;
	}
}
// 牛客js-v8 处理输入输出
let line1 = readline();
let line2 = readline();
let [n, w] = line1.split(' ').map(x => +x);
let v = line2.split(' ').map(x => +x);
let res = ways(v, w);
print(res);

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int bag = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        long ways = ways(arr, bag);
        System.out.println(ways);
        sc.close();
    }

    /**
     * 分治统计有多少种零食的拿法。
     */
    private static long ways(int[] arr, int bag) {
        int N = arr.length;
        int mid = arr.length-1 >> 1;
        SBTSet<Long> leftSet = new SBTSet<>();
        process(arr, bag, 0, mid, 0L,leftSet);
        SBTSet<Long> rightSet = new SBTSet<>();
        process(arr, bag, mid+1, arr.length-1, 0L, rightSet);

        int ans = 0;
        for (int i = 0; i < leftSet.size(); i++) {
            Long leftWeight = leftSet.getIndexKey(i);
            ans += rightSet.lessEqualsCount(bag - leftWeight);
        }
        return ans;
    }

    /**
     * 当前来到i位置，背包内放入了preSum体积的零食，
     * 将i..end的所有选择后的体积放入set，但要求总体积不能超过bag
     * 如果当前来到end+1位置，set添加preSum后返回。
     * 尝试不拿当前位置零食，递归调用(i+1, preSum)
     * 如果arr[i]+preSum<=bag, 递归调用(i+1, preSum+arr[i])
     */
    private static void process(int[] arr, int bag, int i, int end, Long preSum, SBTSet<Long> set) {
        if(i == end+1){
            set.put(preSum);
            return;
        }
        process(arr, bag, i+1,end, preSum, set);
        if(arr[i]+preSum<=bag){
            process(arr, bag, i+1,end, preSum+arr[i], set);
        }
    }

    public static class SBTNode<K extends Comparable<K>>{
        public K key;
        public int all;
        public int size;
        public SBTNode l;
        public SBTNode r;
        public SBTNode(K k){
            key = k;
            size = 1;
            all = 1;
        }
    }

    public static class SBTSet<K extends Comparable<K>>{
        private SBTNode<K> root;

        public int size(){
            return getAll(root);
        }

        /**
         * 放入一个数据。
         */
        public void put(K key){
            root = add(root, key);
        }

        /**
         * 在cur树上新增节点，值为key。
         */
        private SBTNode<K> add(SBTNode<K> cur, K key) {
            if(cur==null) return new SBTNode<>(key);
            cur.all++;
            if(key.compareTo(cur.key)==0) return cur;
            if(key.compareTo(cur.key)<0){
                cur.l = add(cur.l, key);
            }else {
                cur.r = add(cur.r, key);
            }
            cur.size = getSize(cur.l)+getSize(cur.r)+1;
            return maintain(cur);
        }

        /**
         * 调整cur节点的平衡性并返回新节点。
         *
         */
        private SBTNode<K> maintain(SBTNode<K> cur) {
            int ls = getSize(cur.l);
            int lls = 0;
            int lrs = 0;
            if(cur.l != null){
                lls = getSize(cur.l.l);
                lrs = getSize(cur.l.r);
            }
            int rs = getSize(cur.r);
            int rrs = 0;
            int rls = 0;
            if(cur.r != null){
                rrs = getSize(cur.r.r);
                rls = getSize(cur.r.l);
            }

            if(lls>rs){
                cur = rightRotate(cur);
                cur.r = maintain(cur.r);
                cur = maintain(cur);
            }else if(lrs>rs){
                cur.l = leftRotate(cur.l);
                cur = rightRotate(cur);
                cur.l = maintain(cur.l);
                cur.r= maintain(cur.r);
                cur = maintain(cur);
            }else if(rrs>ls){
                cur = leftRotate(cur);
                cur.l = maintain(cur.l);
                cur = maintain(cur);
            }else if(rls>ls){
                cur.r = rightRotate(cur.r);
                cur = leftRotate(cur);
                cur.l = maintain(cur.l);
                cur.r = maintain(cur.r);
                cur = maintain(cur);
            }

            return cur;
        }

        /**
         * 左旋
         */
        private SBTNode<K> leftRotate(SBTNode<K> cur) {
            int same = cur.all - getAll(cur.l) - getAll(cur.r);
            SBTNode<K> right = cur.r;
            cur.r = right.l;
            right.l = cur;
            right.size = cur.size;
            cur.size = getSize(cur.l)+getSize(cur.r)+1;
            right.all = cur.all;
            cur.all = getAll(cur.l)+getAll(cur.r)+same;
            return right;
        }

        private int getAll(SBTNode<K> cur) {
            return cur==null?0:cur.all;
        }

        /**
         * 右旋
         */
        private SBTNode<K> rightRotate(SBTNode<K> cur) {
            int same = cur.all - getAll(cur.l) - getAll(cur.r);
            SBTNode left = cur.l;
            cur.l = left.r;
            left.r = cur;
            left.size = cur.size;
            cur.size = getSize(cur.l)+getSize(cur.r)+1;
            left.all = cur.all;
            cur.all = getAll(cur.l)+getAll(cur.r)+same;
            return left;
        }

        private int getSize(SBTNode cur) {
            return cur==null?0:cur.size;
        }

        /**
         * 返回小于等于指定值的个数。
         * 从root开始向下滑。
         * 等于返回答案。
         * 向右滑收集答案。
         * 向左滑不收集。
         */
        public int lessEqualsCount(K key){
            SBTNode<K> cur = root;
            int ans = 0;
            while (cur!=null){
                if(key.compareTo(cur.key)==0) return ans+cur.all-getAll(cur.r);
                if(key.compareTo(cur.key)<0){
                    cur = cur.l;
                }else {
                    ans += cur.all-getAll(cur.r);
                    cur = cur.r;
                }
            }
            return ans;
        }

        /**
         * 返回排序后位于指定位置的key
         * 检查key是否超出集合范围。
         * 从root向下滑。
         * 如果小于左树all范围，来到左树找。
         * 如果大于等于cur.all-右树.all,去右树找。
         * 否则，返回当前值。
         */
        public K getIndexKey(int index){
            if(index<0 || index>=getAll(root)) throw new RuntimeException("out of range");
            return getIndex(root, index).key;
        }

        /**
         * 返回cur树上的第k个节点。
         */
        private SBTNode<K> getIndex(SBTNode<K> cur, int index){
            if(index<getAll(cur.l)){
                return getIndex(cur.l, index);
            }else if(index >= cur.all-getAll(cur.r)){
                return getIndex(cur.r, index-(cur.all-getAll(cur.r)));
            }else {
                return cur;
            }
        }
    }
}

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		int n=sc.nextInt();
		int w=sc.nextInt();
		int[] v=new int[n+1];
		for(int i=1;i<=n;i++) {
			v[i]=sc.nextInt();
		}
		//初始化
		int[][] dp=new int[n+1][w+1] ;
//		for(int i=0;i<n+1;i++) {
//			for(int j=0;j<w+1;j++) {
//				dp[i][j]=1;
//			}
//		}
        int res=0;
		dp[1][w]=1;
		for(int i=0;i<=w;i++) {
			if(i==w-v[1]) {
				dp[1][i]=1;
			}
		}
        if(n==1){
            if(v[1]<=w){
                System.out.println(2);
            }else{
                System.out.println(1);
            }
            return ;
        }else{
            for(int i=2;i<=n;i++) {
			for(int k=0;k<=w;k++) {
				dp[i][k]=dp[i-1][k]+(k+v[i]<=w?dp[i-1][v[i]+k]:0);
                //我估计就是这个v[i]+k  导致越界了
			}
		}
//		for(int i=1;i<=n;i++) {
//			for(int k=0;k<=w;k++) {
//				System.out.print(dp[i][k]+" ");
//			}
//			System.out.println();
//		}
		
		for(int i=0;i<=w;i++) {
			res+=dp[n][i];
		}
		System.out.println(res);
        }
		
	}
}