結果

問題 No.584 赤、緑、青の色塗り
ユーザー 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
提出日時 2017-10-28 00:11:41
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 2,480 bytes
コンパイル時間 1,949 ms
コンパイル使用メモリ 77,904 KB
実行使用メモリ 47,024 KB
最終ジャッジ日時 2024-05-01 18:13:30
合計ジャッジ時間 8,449 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 98 ms
47,024 KB
testcase_01 AC 116 ms
41,156 KB
testcase_02 AC 104 ms
41,052 KB
testcase_03 AC 113 ms
41,608 KB
testcase_04 AC 108 ms
41,472 KB
testcase_05 AC 114 ms
40,960 KB
testcase_06 AC 100 ms
40,436 KB
testcase_07 AC 111 ms
41,016 KB
testcase_08 AC 106 ms
40,112 KB
testcase_09 AC 98 ms
39,792 KB
testcase_10 AC 113 ms
41,480 KB
testcase_11 AC 101 ms
40,016 KB
testcase_12 AC 115 ms
40,988 KB
testcase_13 AC 118 ms
41,028 KB
testcase_14 AC 211 ms
40,508 KB
testcase_15 AC 110 ms
41,000 KB
testcase_16 AC 218 ms
41,148 KB
testcase_17 AC 230 ms
40,900 KB
testcase_18 AC 155 ms
41,208 KB
testcase_19 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

class Main {
    static final long MOD = 1000000007;
    static final int N = 5000;
    static long[] fact;
    static void initialize() {
	fact = new long[N];
	fact[0] = 1;
	for (int i = 1; i < N; ++i) {
	    fact[i] = (i * fact[i - 1]) % MOD;
	}
    }
    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) {
	    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 tmp = (fact[u] * fact[t]) % MOD;
		long divisor = (fact[rRest] * fact[gRest]) % MOD;
		divisor = (divisor * fact[bRest]) % MOD;
		divisor = (divisor * fact[x]) % MOD;
		divisor = (divisor * fact[y]) % MOD;
		divisor = (divisor * fact[z]) % MOD;
		tmp = (tmp * powerMod(divisor, MOD - 2)) % MOD;
		total = (total + tmp) % 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();
	System.out.println(calculate(n, r, g, b));
    }
}
0