O(N^2)

ChangingChange.java

public class ChangingChange {
	private final long MOD = 1000000007;
	private final int MAX = 1003000;
	private long[] fact, factInv;

	public int[] countWays(int[] ways, int[] valueRemoved, int[] numRemoved) {
		fact = Mod.factorialArray(MAX, MOD);
		factInv = Mod.factorialInverseArray(MAX, MOD,
				Mod.inverseArray(MAX, MOD));

		int D = ways.length - 1;
		int Q = valueRemoved.length;
		int[] ans = new int[Q];
		for (int q = 0; q < Q; q++) {
			int v = valueRemoved[q];// あげるコインの値段
			int n = numRemoved[q];// あげる枚数

			long qAns = 0;
			for (int coins = 0; coins * v <= D; coins++) {
				int value = coins * v;

				// coins枚を使って作られる経路のうち、除かれるn枚のうち1枚以上を使って作られる経路
				long nCr = nCr(n + coins - 1, coins);
				long tmp = ways[D - value] * nCr;
				tmp %= MOD;

				// 包除原理
				if (coins % 2 == 0) {
					qAns += tmp;
					qAns %= MOD;
				} else {
					qAns -= tmp;
					qAns %= MOD;
				}

				if (qAns < 0) {
					qAns += MOD;
				}
			}
			ans[q] = (int) qAns;

		}
		return ans;

	}

	private long nCr(int n, int r) {
		long res = 1;
		res *= fact[n];
		res %= MOD;
		res *= factInv[n - r];
		res %= MOD;
		res *= factInv[r];
		res %= MOD;
		return res;
	}

}

// Mod系ライブラリ
class Mod {
	public static long n(long x, long mod) {
		x %= mod;
		if (x < 0) {
			x += mod;
		}
		return x;
	}

	public static long inverse(long a, long mod) {
		long b = mod, u = 1, v = 0;
		while (b > 0) {
			long temp;
			long t = a / b;
			a -= t * b;
			temp = a;
			a = b;
			b = temp;
			u -= t * v;
			temp = u;
			u = v;
			v = temp;
		}
		return (u % mod + mod) % mod;
	}

	public static long[] inverseArray(int maxN, long modP) {
		long[] inv = new long[maxN + 1];
		inv[1] = 1;
		for (int i = 2; i <= maxN; i++) {
			inv[i] = modP - (modP / i) * inv[(int) (modP % i)] % modP;
		}
		return inv;
	}

	// maxN!の数列を返す　
	public static long[] factorialArray(int maxN, long mod) {
		long[] fact = new long[maxN + 1];
		fact[0] = 1 % mod;
		for (int i = 1; i <= maxN; i++) {
			fact[i] = fact[i - 1] * i % mod;
		}
		return fact;
	}

	// 1/(maxN!)のmodinverseを返す
	public static long[] factorialInverseArray(int maxN, long modP,
			long[] inverseArray) {
		long[] factInv = new long[maxN + 1];
		factInv[0] = 1;
		for (int i = 1; i <= maxN; i++) {
			factInv[i] = factInv[i - 1] * inverseArray[i] % modP;
		}
		return factInv;
	}
}