結果
| 問題 |
No.117 組み合わせの数
|
| コンテスト | |
| ユーザー |
 mikit
|
| 提出日時 | 2018-12-06 03:10:44 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 501 ms / 5,000 ms |
| コード長 | 6,744 bytes |
| コンパイル時間 | 2,562 ms |
| コンパイル使用メモリ | 91,496 KB |
| 実行使用メモリ | 99,928 KB |
| 最終ジャッジ日時 | 2024-09-13 13:29:10 |
| 合計ジャッジ時間 | 4,121 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 1 |
ソースコード
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.util.Objects;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*
* @author mikit
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
LightScanner in = new LightScanner(inputStream);
PrintWriter out = new PrintWriter(outputStream);
D solver = new D();
solver.solve(1, in, out);
out.close();
}
static class D {
public void solve(int testNumber, LightScanner in, PrintWriter out) {
ModMath m = new ModMath();
int t = in.ints();
Factorial f = m.getFactorial(2100000);
for (int i = 0; i < t; i++) {
String s = in.string();
int n = Integer.parseInt(s.substring(2, s.indexOf(',')));
int r = Integer.parseInt(s.substring(s.indexOf(',') + 1, s.indexOf(')')));
switch (s.charAt(0)) {
case 'C':
out.println(f.ncr(n, r));
break;
case 'P':
out.println(f.npr(n, r));
break;
case 'H':
out.println(f.nhr(n, r));
break;
}
}
//*/
/*long n = in.longs(), k = in.longs();
long ans = 1;
for (int i = 0; i < k; i++) {
ans *= (n + i);
ans %= MOD;
}
ModMath m = new ModMath();
for (int i = 2; i<= k; i++) {
System.out.println(m.inv(i));
ans *= m.inv(i);
ans %= MOD;
}
out.println(ans);*/
}
}
static class Vec3i {
public final int x;
public final int y;
public final int z;
public Vec3i(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Vec3i vec3i = (Vec3i) o;
return x == vec3i.x &&
y == vec3i.y &&
z == vec3i.z;
}
public int hashCode() {
return Objects.hash(x, y, z);
}
public String toString() {
return "(" + x + ", " + y + ", " + z + ")";
}
}
static class Vec3l {
private final long x;
private final long y;
private final long z;
public Vec3l(long x, long y, long z) {
this.x = x;
this.y = y;
this.z = z;
}
public long getX() {
return x;
}
public long getY() {
return y;
}
public long getZ() {
return z;
}
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Vec3i vec3i = (Vec3i) o;
return x == vec3i.x &&
y == vec3i.y &&
z == vec3i.z;
}
public int hashCode() {
return Objects.hash(x, y, z);
}
public String toString() {
return "(" + x + ", " + y + ", " + z + ")";
}
}
static class ModMath {
private static final int DEFAULT_MOD = 1_000_000_007;
private final long mod;
public ModMath(long mod) {
this.mod = mod;
}
public ModMath() {
this(DEFAULT_MOD);
}
public long mod(long x) {
x %= mod;
return x < 0 ? x + mod : x;
}
public long inv(long x) {
return mod(LongEuclidSolver.solve(x, -mod).getX());
}
public Factorial getFactorial(int n) {
return new Factorial(this, n);
}
}
static class LightScanner {
private BufferedReader reader = null;
private StringTokenizer tokenizer = null;
public LightScanner(InputStream in) {
reader = new BufferedReader(new InputStreamReader(in));
}
public String string() {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new UncheckedIOException(e);
}
}
return tokenizer.nextToken();
}
public int ints() {
return Integer.parseInt(string());
}
}
static class LongEuclidSolver {
private LongEuclidSolver() {
}
public static Vec3l solve(long p, long q) {
if (q == 0) {
return new Vec3l(p, 1, 0);
}
Vec3l vals = solve(q, p % q);
long a = vals.getY();
long b = vals.getX() - (p / q) * a;
return new Vec3l(a, b, vals.getZ());
}
}
static class Factorial {
private final ModMath mod;
private final int max;
private final long[] natural;
private final long[] reverse;
public Factorial(ModMath mod, int max) {
this.mod = mod;
this.max = max;
this.natural = new long[max];
this.reverse = new long[max];
natural[0] = 1;
for (int i = 1; i < max; i++) {
natural[i] = mod.mod(natural[i - 1] * i);
}
reverse[max - 1] = mod.inv(natural[max - 1]);
for (int i = max - 1; i > 0; i--) {
reverse[i - 1] = mod.mod(reverse[i] * i);
}
}
public long npr(int n, int r) {
return n < r ? 0 : mod.mod(natural[n] * reverse[n - r]);
}
public long ncr(int n, int r) {
return mod.mod(npr(n, r) * reverse[r]);
}
public long nhr(int n, int r) {
return (n | r) == 0 ? 1 : ncr(n + r - 1, r);
}
public String toString() {
return "Factorial{" +
"natural=" + Arrays.toString(natural) +
", reverse=" + Arrays.toString(reverse) +
'}';
}
}
}