結果

問題 No.584 赤、緑、青の色塗り
コンテスト
ユーザー 夕叢霧香(ゆうむらきりか)
提出日時 2017-10-28 01:04:52
言語 Java
(openjdk 23)
結果
AC  
実行時間 519 ms / 2,000 ms
コード長 2,316 bytes
コンパイル時間 6,123 ms
コンパイル使用メモリ 84,464 KB
実行使用メモリ 54,368 KB
最終ジャッジ日時 2024-11-22 00:07:28
合計ジャッジ時間 9,146 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

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;
	int count = r + g + b;
	for (int v = 0; v <= t; ++v) {
	    long tmp = comb(u, r - v);
	    tmp = (tmp * comb(u - r + 2 * v, b - (t - v))) % MOD;
	    tmp = (tmp * comb(t, v)) % 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 > (2 * n + 3) / 3) {
	    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