結果

問題 No.940 ワープ ε=ε=ε=ε=ε=│;p>д<│
ユーザー Shuz*
提出日時 2019-12-03 21:28:18
言語 C++14
(gcc 8.3.0)
結果
WA   .
(最新)
TLE  
(最初)
実行時間 -
コード長 12,903 Byte
コンパイル時間 1,444 ms
使用メモリ 35,784 KB
最終ジャッジ日時 2019-12-04 02:21:02

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
000sample1.txt AC 63 ms
34,032 KB
000sample2.txt AC 62 ms
34,036 KB
000sample3.txt AC 65 ms
34,032 KB
000sample4.txt AC 273 ms
34,300 KB
000sample5.txt WA -
00small.txt AC 86 ms
34,036 KB
01small.txt AC 70 ms
34,032 KB
02small.txt AC 70 ms
34,036 KB
03small.txt AC 68 ms
34,036 KB
04small.txt AC 81 ms
34,036 KB
05small.txt AC 69 ms
34,032 KB
06small.txt AC 64 ms
34,032 KB
07small.txt AC 90 ms
34,036 KB
08small.txt AC 82 ms
34,036 KB
09small.txt AC 62 ms
34,032 KB
10elddim0.txt TLE -
10elddim1.txt -- -
10middle.txt -- -
11middle.txt -- -
12middle.txt -- -
13middle.txt -- -
14middle.txt -- -
30large.txt -- -
31large.txt -- -
32large.txt -- -
33large.txt -- -
99largest.txt -- -
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>
using namespace std;

// Define
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <class T> using pvector = vector<pair<T, T>>;
template <class T>
using rpriority_queue = priority_queue<T, vector<T>, greater<T>>;
constexpr const ll dx[4] = {1, 0, -1, 0};
constexpr const ll dy[4] = {0, 1, 0, -1};
constexpr const ll MOD = 1e9 + 7;
constexpr const ll mod = 998244353;
constexpr const ll INF = 1LL << 60;
constexpr const ll inf = 1 << 30;
constexpr const char rt = '\n';
constexpr const char sp = ' ';
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplase_back
#define elif else if
#define all(a, v, ...)                                                         \
    ([&](decltype((v)) w) { return (a)(begin(w), end(w), ##__VA_ARGS__); })(v)
#define fi first
#define se second

template <class T> bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

// Debug
#define debug(...)                                                             \
    {                                                                          \
        cerr << __LINE__ << ": " << #__VA_ARGS__ << " = ";                     \
        for (auto &&X : {__VA_ARGS__}) cerr << "[" << X << "] ";               \
        cerr << rt;                                                            \
    }

#define dump(a, h, w)                                                          \
    {                                                                          \
        cerr << __LINE__ << ": " << #a << " = [" << rt;                        \
        rep(i, h) {                                                            \
            rep(j, w) cerr << a[i][j] << sp;                                   \
            cerr << rt;                                                        \
        }                                                                      \
        cerr << "]" << rt;                                                     \
    }

#define vdump(a, n)                                                            \
    {                                                                          \
        cerr << __LINE__ << ": " << #a << " = [";                              \
        rep(i, n) cerr << a[i] << (i == n - 1 ? rt : sp);                      \
        cerr << "]" << rt;                                                     \
    }

// Loop
#define inc(i, a, n) for (ll i = (a), _##i = (n); i <= _##i; ++i)
#define dec(i, a, n) for (ll i = (a), _##i = (n); i >= _##i; --i)
#define rep(i, n) for (ll i = 0, _##i = (n); i < _##i; ++i)
#define each(i, a) for (auto &&i : a)

// Stream
#define fout(n) cout << fixed << setprecision(n)
struct io {
    io() { cin.tie(nullptr), ios::sync_with_stdio(false); }
} io;

// Speed
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// Math
inline constexpr ll gcd(const ll a, const ll b) {
    return b ? gcd(b, a % b) : a;
}
inline constexpr ll lcm(const ll a, const ll b) { return a / gcd(a, b) * b; }

inline constexpr ll modulo(const ll n, const ll m = MOD) {
    ll k = n % m;
    return k + m * (k < 0);
}
inline constexpr ll chmod(ll &n, const ll m = MOD) {
    n %= m;
    return n += m * (n < 0);
}
inline constexpr ll mpow(ll a, ll n, const ll m = MOD) {
    ll r = 1;
    rep(i, 64) {
        if (n & (1LL << i)) r *= a;
        chmod(r, m);
        a *= a;
        chmod(a, m);
    }
    return r;
}
inline ll inv(const ll n, const ll m = MOD) {
    ll a = n, b = m, x = 1, y = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        x -= t * y;
        swap(x, y);
    }
    return modulo(x, m);
}

template <ull mod = MOD> struct mi {
    inline constexpr ll modulo(const ll n, const ll m) const noexcept {
        ll k = n % m;
        return k + m * (k < 0);
    }

    ll num;
    inline constexpr mi() noexcept : num() { num = 0; }
    inline constexpr mi(const int n) noexcept : num() { num = modulo(n, mod); }
    inline constexpr mi(const ll n) noexcept : num() { num = modulo(n, mod); }

    inline constexpr mi<mod> inv() const noexcept {
        ll a = num, b = mod, x = 1, y = 0;
        while (b) {
            ll t = a / b;
            a -= t * b;
            swap(a, b);
            x -= t * y;
            swap(x, y);
        }
        return mi<mod>(x);
    }
    inline constexpr mi<mod> inv(ll n) const noexcept {
        ll a = n, b = mod, x = 1, y = 0;
        while (b) {
            ll t = a / b;
            a -= t * b;
            swap(a, b);
            x -= t * y;
            swap(x, y);
        }
        return mi<mod>(x);
    }
    inline constexpr mi<mod> inv(const mi<mod> m) const noexcept {
        return inv(m.num);
    }

    inline constexpr mi<mod> operator+() const noexcept { return mi(num); }
    inline constexpr mi<mod> operator+(const int n) const noexcept {
        return mi<mod>(num + n);
    }
    inline constexpr mi<mod> operator+(const ll n) const noexcept {
        return mi<mod>(num + n);
    }
    inline constexpr mi<mod> operator+(const mi<mod> m) const noexcept {
        return mi<mod>(num + m.num);
    }
    inline constexpr mi<mod> operator-() const noexcept { return -num; }
    inline constexpr mi<mod> operator-(const int n) const noexcept {
        return mi<mod>(num - n);
    }
    inline constexpr mi<mod> operator-(const ll n) const noexcept {
        return mi<mod>(num - n);
    }
    inline constexpr mi<mod> operator-(const mi<mod> m) const noexcept {
        return mi<mod>(num - m.num);
    }
    inline constexpr mi<mod> operator*(const int n) const noexcept {
        return mi<mod>(num * n);
    }
    inline constexpr mi<mod> operator*(const ll n) const noexcept {
        return mi<mod>(num * n);
    }
    inline constexpr mi<mod> operator*(const mi<mod> m) const noexcept {
        return mi<mod>(num * m);
    }
    inline constexpr mi<mod> operator/(const int n) const noexcept {
        return mi<mod>(num * (ll) inv(n));
    }
    inline constexpr mi<mod> operator/(const ll n) const noexcept {
        return mi<mod>(num * (ll) inv(n));
    }
    inline constexpr mi<mod> operator/(const mi<mod> m) const noexcept {
        return mi<mod>(num * (ll) inv(m));
    }
    inline constexpr mi<mod> &operator=(const int n) noexcept {
        num = modulo(n, mod);
        return *this;
    }
    inline constexpr mi<mod> &operator=(const ll n) noexcept {
        num = modulo(n, mod);
        return *this;
    }
    inline constexpr mi<mod> &operator=(const mi<mod> m) noexcept {
        num = m.num;
        return *this;
    }
    inline constexpr mi<mod> &operator+=(const int n) noexcept {
        num = modulo(num + n, mod);
        return *this;
    }
    inline constexpr mi<mod> &operator+=(const ll n) noexcept {
        num = modulo(num + n, mod);
        return *this;
    }
    inline constexpr mi<mod> &operator+=(const mi<mod> m) noexcept {
        num = modulo(num + m.num, mod);
        return *this;
    }
    inline constexpr mi<mod> &operator++() noexcept {
        num = modulo(num + 1, mod);
        return *this;
    }
    inline constexpr mi<mod> operator++(int) noexcept {
        mi &pre = *this;
        num = modulo(num + 1, mod);
        return pre;
    }
    inline constexpr mi<mod> &operator-=(const int n) noexcept {
        num = modulo(num - n, mod);
        return *this;
    }
    inline constexpr mi<mod> &operator-=(const ll n) noexcept {
        num = modulo(num - n, mod);
        return *this;
    }
    inline constexpr mi<mod> &operator-=(const mi<mod> m) noexcept {
        num = modulo(num - m.num, mod);
        return *this;
    }
    inline constexpr mi<mod> &operator--() noexcept {
        num = modulo(num - 1, mod);
        return *this;
    }
    inline constexpr mi<mod> operator--(int) noexcept {
        mi &pre = *this;
        num = modulo(num - 1, mod);
        return pre;
    }
    inline constexpr mi<mod> &operator*=(const int n) noexcept {
        num = modulo(num * n, mod);
        return *this;
    }
    inline constexpr mi<mod> &operator*=(const ll n) noexcept {
        num = modulo(num * n, mod);
        return *this;
    }
    inline constexpr mi<mod> &operator*=(const mi<mod> m) noexcept {
        num = modulo(num * m.num, mod);
        return *this;
    }
    inline constexpr mi<mod> &operator/=(const int n) noexcept {
        num = modulo(num * (ll) inv(n), mod);
        return *this;
    }
    inline constexpr mi<mod> &operator/=(const ll n) noexcept {
        num = modulo(num * (ll) inv(n), mod);
        return *this;
    }
    inline constexpr mi<mod> &operator/=(const mi<mod> m) noexcept {
        num = modulo(num * (ll) inv(m), mod);
        return *this;
    }
    inline constexpr mi<mod> operator==(const int n) const noexcept {
        return num == modulo(n, mod);
    }
    inline constexpr mi<mod> operator==(const ll n) const noexcept {
        return num == modulo(n, mod);
    }
    inline constexpr mi<mod> operator==(const mi<mod> m) const noexcept {
        return num == m.num;
    }
    inline constexpr mi<mod> operator!=(const int n) const noexcept {
        return num != modulo(n, mod);
    }
    inline constexpr mi<mod> operator!=(const ll n) const noexcept {
        return num != modulo(n, mod);
    }
    inline constexpr mi<mod> operator!=(const mi<mod> m) const noexcept {
        return num != m.num;
    }
    constexpr operator int() const noexcept { return num; }
    constexpr operator ll() const noexcept { return num; }
    friend std::istream &operator>>(std::istream &, const mi<> &);
    friend std::ostream &operator<<(std::ostream &, const mi<> &);
};

template <ull mod = MOD>
inline constexpr mi<mod> operator+(const int n, const mi<mod> m) noexcept {
    return mi<mod>(n + m.num);
}
template <ull mod = MOD>
inline constexpr mi<mod> operator+(const ll n, const mi<mod> m) noexcept {
    return mi<mod>(n + m.num);
}
template <ull mod = MOD>
inline constexpr mi<mod> operator-(const int n, const mi<mod> m) noexcept {
    return mi<mod>(n - m.num);
}
template <ull mod = MOD>
inline constexpr mi<mod> operator-(const ll n, const mi<mod> m) noexcept {
    return mi<mod>(n - m.num);
}
template <ull mod = MOD>
inline constexpr mi<mod> operator*(const int n, const mi<mod> m) noexcept {
    return mi<mod>(n * m.num);
}
template <ull mod = MOD>
inline constexpr mi<mod> operator*(const ll n, const mi<mod> m) noexcept {
    return mi<mod>(n * m.num);
}
template <ull mod = MOD>
inline constexpr mi<mod> operator/(const int n, const mi<mod> m) noexcept {
    return mi<mod>(n * (ll) m.inv());
}
template <ull mod = MOD>
inline constexpr mi<mod> operator/(const ll n, const mi<mod> m) noexcept {
    return mi<mod>(n * (ll) m.inv());
}
inline constexpr mi<MOD> operator""_m(ull n) { return mi<MOD>((ll) n); }

template <ull mod = MOD>
inline constexpr mi<mod> pow(mi<mod> m, ll n) noexcept {
    mi<mod> r = mi<mod>(1);
    rep(i, 64) {
        if (n & (1LL << i)) r *= m;
        m *= m;
    }
    return r;
}
template <ull mod> istream &operator>>(istream &is, mi<mod> &m) {
    is >> m.num;
    return is;
}
template <ull mod> ostream &operator<<(ostream &is, mi<mod> &m) {
    is << (ll) m;
    return is;
}

template <ull mod = MOD> struct modmath {
    ll max;
    vector<mi<mod>> fac, inv;
    modmath() : max(1 << 20), fac(max + 1), inv(max + 1) {
        fac[0] = mi<mod>(1);
        rep(i, max) fac[i + 1] = fac[i] * (i + 1);
        inv[max] = fac[max].inv();
        dec(i, max - 1, 0) inv[i] = inv[i + 1] * (i + 1);
    }
    modmath(ll n) : max(n), fac(n + 1), inv(n + 1) {
        fac[0] = 1;
        rep(i, n) fac[i + 1] = fac[i] * (i + 1);
        inv[n] = 1 / fac[n];
        dec(i, n - 1, 0) inv[i] = inv[i + 1] * (i + 1);
    }

    inline mi<mod> fact(ll n) {
        if (n < 0) return mi<mod>(0);
        return fac[n];
    }
    inline mi<mod> perm(ll n, ll r) {
        if (r < 0 || n < r) return mi<mod>(0);
        return fac[n] * inv[n - r];
    }
    inline mi<mod> comb(ll n, ll r) {
        if (r < 0 || n < r) return mi<mod>(0);
        return fac[n] * inv[r] * inv[n - r];
    }
    inline mi<mod> nHr(ll n, ll r) { return comb(n + r - 1, n - 1); }
};

signed main() {
    ll n, x, y, z;
    cin >> x >> y >> z;
    n = x + y + z;
    mi<> res, last, A035317[n];
    modmath<> m(1 << 21);
#define M(i)                                                                   \
    (m.comb(x + i - 1, x) * m.comb(y + i - 1, y) * m.comb(z + i - 1, z))
    rep(i, n) rep(j, i + 1) A035317[i] +=
        (j & 1 ? -1 : 1) * m.comb(n + j - i, j);
    rep(i, n) res += M(n - i) * A035317[i];
    cout << res << rt;
}

// -g -D_GLIBCXX_DEBUG -fsanitize=undefined
0