O(N^3)のDP

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[] dp = new long[D + 1];
			dp[0] = 1;// 0円の作り方は1通り

			for (int j = 1; j <= D; j++) {
				long vanish = 0;
				for (int p = 0; p <= n; p++) {
					// j円を作る方法のうち、v円のコインをp枚使う方法が消滅する
					int value = v * p;
					if (value > j) {
						break;
					}
					vanish += (nCr(n, p) * dp[j - value]) % MOD;
					vanish %= MOD;
				}
				dp[j] = (ways[j] + MOD - vanish) % MOD;
			}

			ans[q] = (int) dp[D];
		}
		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;
	}
}