結果
問題 | No.117 組み合わせの数 |
ユーザー |
|
提出日時 | 2016-05-19 20:12:27 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 831 ms / 5,000 ms |
コード長 | 2,880 bytes |
コンパイル時間 | 3,575 ms |
コンパイル使用メモリ | 79,416 KB |
実行使用メモリ | 100,764 KB |
最終ジャッジ日時 | 2024-10-06 10:21:11 |
合計ジャッジ時間 | 5,931 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 |
ソースコード
import java.io.*;import java.util.*;public class Main_yukicoder117 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);Printer pr = new Printer(System.out);int t = sc.nextInt();preCombi2(2_000_000);for (int i = 0; i < t; i++) {String[] s = sc.next().split("[\\,\\(\\)]");// pr.printf("%s %s %s\n", s[0], s[1], s[2]);switch (s[0]) {case "C":pr.println(C(Integer.parseInt(s[1]), Integer.parseInt(s[2])));break;case "P":pr.println(P(Integer.parseInt(s[1]), Integer.parseInt(s[2])));break;case "H":pr.println(H(Integer.parseInt(s[1]), Integer.parseInt(s[2])));break;}}pr.close();sc.close();}private static int MOD = 1_000_000_007;private static long[] fact;private static long[] ifact;private static void preCombi2(int size) {// cache size need size * 2 * 16.fact = new long[size + 1];fact[0] = 1;for (int i = 1; i <= size; i++) {fact[i] = fact[i - 1] * i % MOD;}ifact = new long[size + 1];ifact[0] = 1;int loop = MOD - 2;long x = fact[size];ifact[size] = 1;while (loop > 0) {if (loop % 2 == 1) {ifact[size] = ifact[size] * x % MOD;}x = x * x % MOD;loop /= 2;}for (int i = size - 1; i >= 0; i--) {ifact[i] = ifact[i + 1] * (i + 1) % MOD;}}private static int C(int n, int r) {if (r > n) {return 0;}return (int)(((fact[n] * ifact[n - r]) % MOD) * ifact[r] % MOD);}private static int P(int n, int r) {if (r > n) {return 0;}return (int)((fact[n] * ifact[n -r]) % MOD);}private static int H(int n, int r) {if (n == 0 && r == 0) {return 1;}return C(n + r - 1, r);}@SuppressWarnings("unused")private static class Scanner {BufferedReader br;Iterator<String> it;Scanner (InputStream in) {br = new BufferedReader(new InputStreamReader(in));}String next() throws RuntimeException {try {if (it == null || !it.hasNext()) {it = Arrays.asList(br.readLine().split(" ")).iterator();}return it.next();} catch (IOException e) {throw new IllegalStateException();}}int nextInt() throws RuntimeException {return Integer.parseInt(next());}long nextLong() throws RuntimeException {return Long.parseLong(next());}float nextFloat() throws RuntimeException {return Float.parseFloat(next());}double nextDouble() throws RuntimeException {return Double.parseDouble(next());}void close() {try {br.close();} catch (IOException e) {// throw new IllegalStateException();}}}private static class Printer extends PrintWriter {Printer(PrintStream out) {super(out);}}}