結果

問題 No.584 赤、緑、青の色塗り
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2017-10-28 00:18:19
言語 Java21
(openjdk 21)
結果
AC  
実行時間 859 ms / 2,000 ms
コード長 2,736 bytes
コンパイル時間 2,637 ms
コンパイル使用メモリ 80,276 KB
実行使用メモリ 54,660 KB
最終ジャッジ日時 2024-11-21 23:58:28
合計ジャッジ時間 6,856 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 141 ms
54,256 KB
testcase_01 AC 123 ms
54,100 KB
testcase_02 AC 131 ms
53,852 KB
testcase_03 AC 135 ms
54,124 KB
testcase_04 AC 138 ms
53,932 KB
testcase_05 AC 151 ms
53,944 KB
testcase_06 AC 172 ms
54,040 KB
testcase_07 AC 136 ms
54,232 KB
testcase_08 AC 125 ms
53,012 KB
testcase_09 AC 135 ms
53,932 KB
testcase_10 AC 136 ms
54,144 KB
testcase_11 AC 138 ms
54,248 KB
testcase_12 AC 132 ms
54,120 KB
testcase_13 AC 137 ms
54,404 KB
testcase_14 AC 196 ms
54,660 KB
testcase_15 AC 137 ms
54,108 KB
testcase_16 AC 154 ms
54,020 KB
testcase_17 AC 166 ms
54,120 KB
testcase_18 AC 155 ms
54,108 KB
testcase_19 AC 859 ms
54,148 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

class Main {
    static final long MOD = 1000000007;
    static final int N = 5000;
    static long[] fact;
    static long[] invfact;
    static void initialize() {
	fact = new long[N];
	invfact = new long[N];
	fact[0] = invfact[0] = 1;
	for (int i = 1; i < N; ++i) {
	    fact[i] = (i * fact[i - 1]) % MOD;
	    invfact[i] = powerMod(fact[i], MOD - 2);
	}
    }
    static long powerMod(long x, long exponent) {
	long prod = 1;
	for (int i = 63; i >= 0; --i) {
	    prod = (prod * prod) % MOD;
	    if ((exponent & 1L << i) != 0) {
		prod = (prod * x) % MOD;
	    }
	}
	return prod;
    }
    static long comb(int x, int y) {
	if (x < 0) {
	    return 0;
	}
	if (y < 0 || y > x) {
	    return 0;
	}
	long r= (fact[x] * powerMod((fact[x - y] * fact[y]) % MOD, MOD - 2)) % MOD;
	return r;
    }
    static long f(int x, int y) {
	if (x == 0) {
	    return y == 0 ? 1 : 0;
	}
	return comb(x - 1, y - 1);
    }
    static long sub(int n, int k, int t) {
	long total = 0;
	if (n - k >= k - t + 1) {
	    total += f(n - k, k - t + 1);
	}
	if (n - k >= k - t) {
	    total += 2 * f(n - k, k - t);
	}
	if (n - k >= k - t - 1) {
	    total += f(n - k, k - t - 1);
	}
	total %= MOD;
	return (comb(k - t, t) * total) % MOD;
    }
    static long helper(int t, int u, int r, int g, int b) {
	long total = 0;
	for (int x = 0; x <= t; ++x) {
	    if (r < x || g < x) {
		continue;
	    }
	    for (int y = 0; y <= t - x; ++y) {
		int z = t - x - y;
		int rRest = r - x - z;
		int gRest = g - x - y;
		int bRest = b - y - z;
		if (rRest < 0 || gRest < 0 || bRest < 0) {
		    continue;
		}
		long divisor = (invfact[rRest] * invfact[gRest]) % MOD;
		divisor = (divisor * invfact[bRest]) % MOD;
		divisor = (divisor * invfact[x]) % MOD;
		divisor = (divisor * invfact[y]) % MOD;
		divisor = (divisor * invfact[z]) % MOD;
		long tmp = divisor;
		total = (total + tmp) % MOD;
	    }
	}
	long multiplier = (fact[u] * fact[t]) % MOD;
	total = (total * multiplier) % MOD;
	return (total * powerMod(2, t)) % MOD;
    }
    static long calculate(int n, int r, int g, int b) {
	initialize();
	int count = r + g + b;
	if (count > n) {
	    return 0;
	}
	long total = 0;
	for (int t = 0; t <= count / 2; ++t) {
	    long res = sub(n, count, t);
	    if (res == 0) {
		continue;
	    }
	    long dat = helper(t, count - 2 * t, r, g, b);
	    long mult = (res * dat) % MOD;
	    total += mult;
	    total %= MOD;
	}
	return total;
    }
    public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int n = scan.nextInt();
	int r = scan.nextInt();
	int g = scan.nextInt();
	int b = scan.nextInt();
	int[] rgb = new int[]{r, g, b};
	Arrays.sort(rgb);
	System.out.println(calculate(n, rgb[0], rgb[1], rgb[2]));
    }
}
0