結果

問題 No.117 組み合わせの数
ユーザー goodbaton
提出日時 2015-08-06 22:37:27
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,524 bytes
コンパイル時間 602 ms
コンパイル使用メモリ 74,160 KB
実行使用メモリ 10,400 KB
最終ジャッジ日時 2024-07-18 03:46:03
合計ジャッジ時間 12,991 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:107:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  107 |     scanf("%d",&t);
      |     ~~~~~^~~~~~~~~
main.cpp:129:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  129 |         scanf(" %c(%d,%d)",&s,&n,&k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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 1024

ll gygen[32000];

ll factorial(int n,int M){
    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 < 32000)
        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<32000;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);
        }
    }
    
    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