3454023_ac_18922ms_103324k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main {
	private Scanner in;
	private int n, M, l, ans;
	private int [] k;
	private int [] p;
	private HashMap <Integer, Integer> hm;

	public static void main(String [] args) {
		new Main().run();
	}

	private void run() {
		in = new Scanner (System.in);

		n = in.nextInt();
		M = in.nextInt();
		k = new int [n];
		ans = 0;
		p = new int [n];
		hm = new HashMap <Integer, Integer> ();
		for (int i = 0; i < n; i++) {
			k[i] = in.nextInt();
			p[i] = in.nextInt();
		}
		l = n >> 1;
		dfs_init(0, 0);
		dfs_find(l, 0);
		System.out.println(ans);
		in.close();
	}

	private void dfs_find(int v, int sum) {
		if (v == n) {
			if (hm.containsKey(-sum)) {
				ans += hm.get(-sum);
			}
			return ;
		}
		for (int i = 1; i <= M; i++) {
			dfs_find(v + 1, sum + k[v] * power(i, p[v]));
		}
	}

	private void dfs_init(int v, int sum) {
		if (v == l) {
			int cnt = 0;
			if (hm.containsKey(sum)) {
				cnt = hm.get(sum);
			}
			hm.put(sum, cnt + 1);
			return ;
		}
		for (int i = 1; i <= M; i++) {
			dfs_init(v + 1, sum + k[v] * power(i, p[v]));
		}
	}

	private int power(int a, int b) {
		int ret = 1;

		for (int i = 0; i < b; i++) {
			ret *= a;
		}
		return ret;
	}
}