結果
| 問題 | No.117 組み合わせの数 |
| ユーザー |
 t8m8⛄️
|
| 提出日時 | 2015-03-14 08:11:08 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 5,804 bytes |
| コンパイル時間 | 3,186 ms |
| コンパイル使用メモリ | 78,904 KB |
| 実行使用メモリ | 68,160 KB |
| 最終ジャッジ日時 | 2024-06-28 22:53:19 |
| 合計ジャッジ時間 | 3,972 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
ソースコード
//No.117 組み合わせの数
import java.util.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.lang.Math.*;
public class No117 {
static final InputStream in = System.in;
static final PrintWriter out = new PrintWriter(System.out,false);
static void solve(){
final int MOD = 1000000007;
init(1000000,MOD);
//trace(factInv);
int t = nextInt();
while (t-- > 0) {
String s = next();
int n = Integer.parseInt(s.substring(2,s.indexOf(',')));
int k = Integer.parseInt(s.substring(s.indexOf(',')+1,s.indexOf(')')));
switch(s.charAt(0)) {
case 'C': out.println(combination(n,k,MOD)); break;
case 'P': out.println(permutation(n,k,MOD)); break;
case 'H': out.println(homogeneous(n,k,MOD)); break;
}
}
}
// int i,j;m=md;s=small;
// f=(int*)mem;
// v=f+lim;
// d=(int**)(v+lim);
// d[0]=(int*)(d+s);
// REP(i,1,s)d[i]=d[i-1]+s;
// mem=(void*)(d[0]+s*s);
// f[0]=1;
// REP(i,1,lim)f[i]=(ll)f[i-1]*i%m;
// v[lim-1]=get_inv(f[lim-1],m);
// for(i=lim-1;i;i--) v[i-1]=(ll)v[i]*i%m;
// REP(i,1,s) d[0][i]=0;
// rep(i,s) d[i][0]=1;
// REP(i,1,s)
// REP(j,1,s)
// {d[i][j]=d[i-1][j-1]+d[i-1][j];
// if(d[i][j]>=m)d[i][j]-=m;}
// return mem
static long[] extgcd(long a, long b) {
if (a == 0 || b == 0) return null;
int asig = Long.signum(a);
int bsig = Long.signum(b);
a = abs(a); b = abs(b);
long x = 1, y = 0;
long p = 0, q = 1;
while (b > 0) {
long c = a/b, d = a;
a = b; b = d % b;
d = x; x = p; p = d - c*p;
d = y; y = q; q = d - c*q;
}
return new long[]{a,x*asig,y*bsig};
}
static long modInverse(long a, long m) {
long[] gcd = extgcd(a,m);
if (gcd[0] != 1) return 0;
return (m+gcd[1]%m)%m;
}
static long[] fact;
static long[] factInv;
static void init(int n,int p) {
fact = new long[n+1]; factInv = new long[n+1];
fact[0] = fact[1] = 1;
for (int i=2; i<=n; i++) fact[i] = fact[i-1]*i%p;
factInv[n] = modInverse(fact[n],p);
for (int i=n; i>0; i--) factInv[i-1] = factInv[i]*i%p;
}
static int combination(int n, int r, int p) {
if (n < r || r < 0) return 0;
return (int)(fact[n]*factInv[r]%p*factInv[n-r]%p);
}
static int permutation(int n, int r, int p) {
if (n < r || r < 0) return 0;
return (int)(fact[n]*factInv[n-r]%p);
}
static int homogeneous(int n, int r, int p) {
if (n == 0 && r == 0) return 1;
return combination(n+r-1,r,p);
}
public static void main(String[] args) throws Exception {
long start = System.currentTimeMillis();
solve();
out.flush();
long end = System.currentTimeMillis();
//trace(end-start + "ms");
in.close();
}
static void trace(Object... o) { System.out.println(deepToString(o));}
static final byte[] buf = new byte[1024];
static int ptr = 0;
static int buflen = 0;
static boolean hasNextByte() {
if (ptr < buflen)
return true;
ptr = 0;
try{
buflen = in.read(buf);
}catch (IOException e) {e.printStackTrace();}
if (buflen <= 0)
return false;
return true;
}
static int readByte() { if (hasNextByte()) return buf[ptr++]; else return -1;}
static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
static void skip() { while(hasNextByte() && !isPrintableChar(buf[ptr])) ptr++;}
static boolean hasNext() {skip(); return hasNextByte();}
static String next() {
if (!hasNext()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
static long nextLong() {
if (!hasNext()) throw new NoSuchElementException();
boolean minus = false;
long num = readByte();
if(num == '-'){
num = 0;
minus = true;
}else if (num < '0' || '9' < num){
throw new NumberFormatException();
}else{
num -= '0';
}
while(true){
int b = readByte();
if('0' <= b && b <= '9')
num = num * 10 + (b - '0');
else if(b == -1 || !isPrintableChar(b))
return minus ? -num : num;
else
throw new NoSuchElementException();
}
}
static int nextInt() {
long num = nextLong();
if (num < Integer.MIN_VALUE || Integer.MAX_VALUE < num)
throw new NumberFormatException();
return (int)num;
}
static double nextDouble() {
return Double.parseDouble(next());
}
static char nextChar() {
if (!hasNext()) throw new NoSuchElementException();
return (char)readByte();
}
static String nextLine() {
while (hasNextByte() && (buf[ptr] == '\n' || buf[ptr] == '\r')) ptr++;
if (!hasNextByte()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (b != '\n' && b != '\r') {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
static int[] nextArrayInt(int n) {
int[] a = new int[n];
for (int i=0; i<n; i++) a[i] = nextInt();
return a;
}
}