結果

問題 No.117 組み合わせの数
ユーザー goodbatongoodbaton
提出日時 2015-08-06 22:46:50
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,713 ms / 5,000 ms
コード長 2,880 bytes
コンパイル時間 562 ms
コンパイル使用メモリ 73,496 KB
実行使用メモリ 34,668 KB
最終ジャッジ日時 2023-09-25 04:21:28
合計ジャッジ時間 4,505 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,713 ms
34,668 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cstring>

typedef long long ll;
using namespace std;

#define mod 1000000007
#define INF 1000000000
#define LLINF 2000000000000000000LL
#define PI 3.1415926536

#define SIZE 2000001

ll gygen[SIZE];
ll fac[SIZE];

ll factorial(int n,int M){
    
    return fac[n];
    
    ll ret = 1;
    if(n<=1) return 1;
    
    for(int i=1;i<=n;i++){
        ret = (ret*i)%M;
    }
    
    return ret;
}

ll power(int k,int n,int M){
    if(n==0) return 1;
    if(n==1) return (ll)k;
    
    ll ret = power(k,n/2,M);
    
    ret=(ret*ret)%M;
    
    if(n%2==1)
        ret=(ret*k)%M;
    
    return ret;
}

ll get_gygen(int k){
    int ret;
    
    if(k < SIZE)
        return gygen[k];
    
    for(int j=2;j*j<=k;j++){
        if(k%j==0){
            return (get_gygen(j)*get_gygen(k/j))%mod;
        }
    }
    
    return power(k,mod-2,mod);
}

ll get_fac(int k){
    int ret;
    
    if(k < SIZE)
        return gygen[k];
    
    for(int j=2;j*j<=k;j++){
        if(k%j==0){
            return (get_gygen(j)*get_gygen(k/j))%mod;
        }
    }
    
    return power(k,mod-2,mod);
}

//nCm (mod p) p is prime number
int C(int n,int m,int M){
    if(n<m) return 0;
    
    if(m==0 || n==m) return 1;
    
    ll chi = factorial(n,M);
    ll mot = (factorial(m,M) * factorial(n-m,M))%M;
    
    
    mot = get_gygen((int)mot);
    
    ll ret = (chi*mot)%M;
    
    return (int)ret;
}

int P(int n,int m,int M){
    if(n<m) return 0;
    
    if(m==0) return 1;
    
    ll chi = factorial(n,M);
    ll mot = factorial(n-m,M);
    
    
    mot = get_gygen((int)mot);
    
    ll ret = (chi*mot)%M;
    
    return (int)ret;
}

int H(int n,int m,int M){
    if(n==0 && m==0) return 1;
    return C(n+m-1,m,M);
}

int main(){
    int t,n,k;
    char s;
    scanf("%d",&t);
    
    gygen[0]=0;
    gygen[1]=1;
    
    for(int i=2;i<SIZE;i++){
        bool f = true;
        
        for(int j=2;j*j<=i;j++){
            if(i%j==0){
                gygen[i] = (gygen[j]*gygen[i/j])%mod;
                f=false;
                break;
            }
        }
        
        if(f){
            gygen[i] = power(i,mod-2,mod);
        }
    }
    
    fac[0]=1;
    for(ll i=1;i<SIZE;i++) fac[i]=(fac[i-1]*i)%mod;
    
    for(int i=0;i<t;i++){
        scanf(" %c(%d,%d)",&s,&n,&k);
        
        if(s=='C'){
            //fprintf(stderr,"C(%d,%d) = ",n,k);
            printf("%d\n",C(n,k,mod));
        }
        if(s=='P'){
            //fprintf(stderr,"P(%d,%d) = ",n,k);
            printf("%d\n",P(n,k,mod));
        }
        if(s=='H'){
            //fprintf(stderr,"H(%d,%d) = ",n,k);
            printf("%d\n",H(n,k,mod));
        }
    }
    
    return 0;
}
0