結果

問題 No.117 組み合わせの数
ユーザー john_doe_113john_doe_113
提出日時 2015-06-27 02:59:19
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 593 ms / 5,000 ms
コード長 1,908 bytes
コンパイル時間 518 ms
コンパイル使用メモリ 59,328 KB
実行使用メモリ 238,336 KB
最終ジャッジ日時 2024-07-07 19:53:22
合計ジャッジ時間 2,018 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <string>
#define mo 1000000007
#define ll long long
using namespace std;

ll factlist[10000001] = {};
ll factlistr[10000001] = {};
ll factlistinv[10000001] = {};

ll C(int num1, int num2);
ll P(int num1, int num2);
ll H(int num1, int num2);

int main() {

    int n = 0;
    cin >> n;

    char * c = (char *)malloc(sizeof(char) * n);
    int * num1 = (int *)malloc(sizeof(int) * n);
    int * num2 = (int *)malloc(sizeof(int) * n);

    for (int i = 0; i < n; i++){
        static string temp("");
        cin >> temp;

        c[i] = temp.c_str()[0];
        num1[i] = atoi(temp.substr(2,temp.find(",")-2).c_str());
        num2[i] = atoi(temp.substr(temp.find(",")+1,temp.find(")")-temp.find(",")+1).c_str());
    }

    factlistinv[1] = 1;
    for (int i = 2; i < 10000001; i++){
        factlistinv[i] = (mo - (mo/i) * factlistinv[mo%i] % mo) % mo;
    }
    /*この逆元の部分だけわからん！誰か教えて！*/
    factlist[0] = 1;
    factlistr[0] = 1;
    for (int i = 1; i < 10000001; i++){
        factlist[i] = (factlist[i - 1] * i) % mo;
        factlistr[i] = (factlistr[i - 1] * factlistinv[i]) % mo;
    }
    for (int i = 0; i < n; i++){
        switch (c[i]) {
            case 'C':
            cout << C(num1[i],num2[i]) << endl;
                break;
            case 'P':
            cout << P(num1[i],num2[i]) << endl;
                break;
            case 'H':
            cout << H(num1[i],num2[i])  << endl;
                break;
        }
    }
    free(c);
    free(num1);
    free(num2);
	return 0;
}



ll C(int num1, int num2){
    return num1 < num2 ? 0 : ((((factlist[num1])*(factlistr[num1-num2])) % mo)*(factlistr[num2])) % mo;
}

ll P(int num1, int num2){
    return num1 < num2 ? 0 : (factlist[num1])*(factlistr[num1-num2]) % mo;
}

ll H(int num1, int num2){
    return ((num1 == 0) && (num2 == 0)) ? 1 : C(num1+num2-1,num2);
}
0