TopCoder SRM 663 Div1 Medium: ChangingChange
解法
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; } }