結果

問題 No.895 MESE
ユーザー mamekin
提出日時 2019-09-27 21:54:00
言語 C++14
(gcc 8.3.0)
結果
AC  
実行時間 30 ms
コード長 2,252 Byte
コンパイル時間 993 ms
使用メモリ 8,428 KB
最終ジャッジ日時 2019-11-16 16:11:39

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0sample00.txt AC 3 ms
1,496 KB
0sample01.txt AC 3 ms
1,496 KB
0sample02.txt AC 3 ms
1,508 KB
1small00.txt AC 3 ms
1,496 KB
1small01.txt AC 3 ms
1,500 KB
1small02.txt AC 3 ms
1,500 KB
1small03.txt AC 4 ms
1,504 KB
1small04.txt AC 3 ms
1,500 KB
2medium00.txt AC 3 ms
1,536 KB
2medium01.txt AC 3 ms
1,528 KB
2medium02.txt AC 3 ms
1,544 KB
2medium03.txt AC 3 ms
1,556 KB
2medium04.txt AC 4 ms
1,528 KB
3large00.txt AC 18 ms
5,524 KB
3large01.txt AC 19 ms
5,256 KB
3large02.txt AC 22 ms
5,788 KB
3large03.txt AC 18 ms
4,992 KB
3large04.txt AC 15 ms
5,260 KB
3large05.txt AC 29 ms
8,428 KB
3large06.txt AC 30 ms
8,424 KB
3large07.txt AC 30 ms
8,428 KB
3large08.txt AC 30 ms
8,424 KB
3large09.txt AC 30 ms
8,424 KB
3large10.txt AC 30 ms
8,428 KB
3large11.txt AC 29 ms
8,424 KB
3large12.txt AC 29 ms
8,428 KB
3large13.txt AC 29 ms
8,424 KB
3large14.txt AC 29 ms
8,424 KB
3large15.txt AC 29 ms
8,428 KB
テストケース一括ダウンロード

ソースコード

diff #
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

void mod_inverse(int n, vector<long long>& inv, int mod)
{
    inv.assign(n+1, -1);
    inv[1] = 1;
    for(int i=2; i<=n; ++i)
        inv[i] = inv[mod % i] * (mod - mod / i) % mod;
}

class FactorialCalculation
{
private:
    const int mod;
    vector<long long> factorial;
    vector<long long> invFactorial;
public:
    FactorialCalculation(int n, int mod) : mod(mod)
    {
        factorial.resize(n+1, 1);
        invFactorial.resize(n+1, 1);
        vector<long long> inv;
        mod_inverse(n, inv, mod);
        for(int i=1; i<=n; ++i){
            factorial[i] = factorial[i-1] * i % mod;
            invFactorial[i] = invFactorial[i-1] * inv[i] % mod;
        }
    }
    long long getFactorial(int n){
        return factorial[n];
    }
    long long getInvFactorial(int n){
        return invFactorial[n];
    }
    long long getPermutation(int n, int r){
        if(n < r)
            return 0;
        return factorial[n] * invFactorial[n-r] % mod;
    }
    long long getCombination(int n, int r){
        if(n < r)
            return 0;
        return getPermutation(n, r) * invFactorial[r] % mod;
    }
    long long getHomogeneous(int n, int r){
        return getCombination(n+r-1, r);
    }
};

const int MOD = 1000000007;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;

    int n = a + b + c;
    FactorialCalculation fc(n, MOD);

    long long ans = 0;
    long long num = 1;
    for(int i=n-1; i>=1; --i){
        if(i <= a){
            long long tmp = fc.getCombination(n-2-i, c-1);
            tmp *= fc.getCombination(n-1-i-c, b-1);
            tmp %= MOD;
            ans += (num - 1) * tmp;
            ans %= MOD;
        }
        num *= 2;
        num %= MOD;
    }
    cout << ans << endl;

    return 0;
}
0