結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 122 ms
46,416 KB
testcase_01 AC 124 ms
41,588 KB
testcase_02 AC 112 ms
40,396 KB
testcase_03 AC 124 ms
41,584 KB
testcase_04 AC 109 ms
40,132 KB
testcase_05 AC 122 ms
41,548 KB
testcase_06 AC 123 ms
41,540 KB
testcase_07 AC 111 ms
40,364 KB
testcase_08 AC 119 ms
41,452 KB
testcase_09 AC 125 ms
41,380 KB
testcase_10 AC 124 ms
41,400 KB
testcase_11 AC 112 ms
40,260 KB
testcase_12 AC 123 ms
41,608 KB
testcase_13 AC 124 ms
41,512 KB
testcase_14 AC 222 ms
41,580 KB
testcase_15 AC 130 ms
41,544 KB
testcase_16 AC 279 ms
41,516 KB
testcase_17 AC 245 ms
40,624 KB
testcase_18 AC 179 ms
41,540 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 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;
		long tmp = powerMod(divisor, MOD - 2);
		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();
	System.out.println(calculate(n, r, g, b));
    }
}
0