結果

問題 No.895 MESE
ユーザー e869120
提出日時 2019-09-15 13:57:35
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 336 ms / 2,000 ms
コード長 1,937 bytes
コンパイル時間 522 ms
コンパイル使用メモリ 67,148 KB
実行使用メモリ 12,968 KB
最終ジャッジ日時 2024-07-06 22:43:52
合計ジャッジ時間 10,879 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
using namespace std;
long long modpow(long long a, long long b, long long m) {
    long long p = 1, q = a;
    for (int i = 0; i < 30; i++) {
        if ((b &(1LL << i)) != 0) { p *= q; p %= m; }
        q *= q; q %= m;
    }
    return p;
}
long long Div(long long a, long long b, long long m) {
    return (a * modpow(b, m - 2, m)) % m;
}
long long mod = 1000000007;
long long fact[300009], factinv[300009], inv[300009], power2[300009];
long long A, B, C;
void init() {
    fact[0] = 1;
    for (int i = 1; i <= 300000; i++) fact[i] = (1LL * i * fact[i - 1]) % mod;
    for (int i = 0; i <= 300000; i++) factinv[i] = Div(1, fact[i], mod);
    for (int i = 1; i <= 300000; i++) inv[i] = Div(1, i, mod);
    power2[0] = 1;
    for (int i = 1; i <= 300000; i++) power2[i] = (2LL * power2[i - 1]) % mod;
}
long long ncr(long long n, long long r) {
    if (n < r || r < 0) return 0LL;
    return (fact[n] * factinv[r] % mod) * factinv[n - r] % mod;
}
int main() {
    init();
    cin >> A >> B >> C;
    // Y の合計を求める
    long long Y = 0, TotalWays = 0;
    for (int i = 1; i <= A; i++) {
        long long Y1 = power2[A + B + C - i - 1] - 1LL;
        long long Y2 = (B - 1LL) * inv[A + B + C - i - 1] % mod;
        long long Y3 = ncr(B + C - 1, B - 1) * ncr(A + B + C - i - 1, A - i) % mod;
        long long YY = (Y1 * Y2 % mod) * Y3 % mod;
        Y += YY; Y %= mod;
        Y += power2[A + B + C - i - 1] * Y3 % mod; Y %= mod;
        TotalWays += Y3; TotalWays %= mod;
    }
    // X の合計を求める
    long long X1 = power2[A + B + C - 1] - 1LL;
    long long X2 = (A - 1LL) * inv[A + B + C - 1] % mod;
    long long X3 = TotalWays;
    long long X = 0;
    X += (X1 * X2 % mod) * X3 % mod;
    X += power2[A + B + C - 1] * X3 % mod;
    X %= mod;
    // X + Y + Z の合計を求める
    long long Total = 0;
    long long T1 = TotalWays;
    long long T2 = power2[A + B + C] - 1LL;
    Total = T1 * T2 % mod;
    // 最後に出力する
    long long Answer = (Total - X - Y + mod * 2LL) % mod;
    cout << Answer << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0