結果

問題 No.584 赤、緑、青の色塗り
コンテスト
ユーザー 夕叢霧香(ゆうむらきりか)
提出日時 2017-10-28 00:13:16
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 13 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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