結果

問題 No.895 MESE
ユーザー kcvlexkcvlex
提出日時 2019-09-27 21:57:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 29 ms / 2,000 ms
コード長 3,283 bytes
コンパイル時間 1,806 ms
コンパイル使用メモリ 170,760 KB
実行使用メモリ 26,736 KB
最終ジャッジ日時 2024-09-24 10:49:56
合計ジャッジ時間 3,490 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:86:74: warning: iteration 500000 invokes undefined behavior [-Waggressive-loop-optimizations]
   86 |     for(ll i = 0; i <= size; i++) pow2_sum[i + 1] = (pow2_sum[i] + pow2[i]) % mod;
      |                                                                    ~~~~~~^
main.cpp:86:21: note: within this loop
   86 |     for(ll i = 0; i <= size; i++) pow2_sum[i + 1] = (pow2_sum[i] + pow2[i]) % mod;
      |                   ~~^~~~~~~

ソースコード

diff # 

// #define DEBUGGING
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()

template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
using ll = int64_t;
using ull = uint64_t;
using PLL = pair<ll, ll>;

template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); }

namespace init__ {

struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

}

#ifdef DEBUGGING
// #include "../debug/debug.cpp"
#include "../../debug/debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif

template <typename T>
T make_v(T init) { return init; }

template <typename T, typename... Tail>
auto make_v(T init, size_t s, Tail... tail) {
#define rec make_v(init, tail...)
    return V<decltype(rec)>(s, rec);
#undef rec
}

const ll mod = 1e9 + 7;

template <ll MOD>
class Combination {
private:
    ll N;
    V<ll> factv, rfactv;

public:
    Combination<MOD>(ll N) : N(N), factv(N + 1, 1), rfactv(N + 1) {
        for(ll i = 1; i <= N; i++) factv[i] = factv[i - 1] * i % MOD;
        rfactv.back() = inv(factv.back());
        for(ll i = N - 1; 0 <= i; i--) rfactv[i] = (i + 1) * rfactv[i + 1] % MOD;
    }

    ll fact(ll n) { return factv[n]; }

    ll rfact(ll n) { return rfactv[n]; }

    ll pow(ll a, ll b) { return b ? (b & 1 ? a : 1) * pow(a * a % MOD, b / 2) % MOD : 1; }

    ll inv(ll a) { return pow(a, MOD - 2); }

    ll comb(ll n, ll k) { return factv[n] * rfactv[n - k] % MOD * rfactv[k] % MOD; }
};

const size_t size = 5e5;
Combination<mod> C(1e6 + 10);
ll pow2[size] = { 1 };
ll pow2_sum[size + 1];

int main() {
    for(ll i = 1; i < size; i++) pow2[i] = 2 * pow2[i - 1] % mod;
    for(ll i = 0; i <= size; i++) pow2_sum[i + 1] = (pow2_sum[i] + pow2[i]) % mod;
    ll a, b, c;
    cin >> a >> b >> c;
    ll abc = a + b + c;
    ll ans = 0;
    for(ll i = 1; i <= a; i++) {
        ll rest = abc - i - 1;
        ll sum = pow2_sum[rest];
        rest--;
        ll rest_a = a - i;
        DEBUG(rest);
        ll rest_comb = C.comb(rest, rest_a);
        rest -= rest_a;
        DEBUG(rest);
        (rest_comb *= C.comb(rest, b - 1)) %= mod;
        DEBUG(rest_comb);
        (sum *= rest_comb) %= mod;
        DEBUG(make_tuple(rest_comb, pow2_sum[rest + 1]));
        ans += sum;
        DEBUG(make_tuple(abc, rest, pow2_sum[abc - rest]));
    }
    cout << ans % mod << endl;
    return 0;
}
0