TopCoder SRM 663 Div1 Medium: ChangingChange

解法

mayokoex.hatenablog.com

D円を作る方法のうち、消えるものをDPして求めると、答えを導き出すことができるが時間がかかりすぎてしまう。

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];
}

そこで、包除原理を使うとループをひとつ減らす事ができ、大幅に高速化することが出来る。

コード

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;
	}
}