#417684 (C++14) No.940 ワープ　ε=ε=ε=ε=ε=│;p>д＜│

提出ソース

結果

問題	No.940 ワープ　ε=ε=ε=ε=ε=│;p>д＜│
ユーザー	jell
提出日時	2020-01-15 17:07:16
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	512 ms / 5,000 ms
コード長	7,953 bytes
コンパイル時間	584 ms
コンパイル使用メモリ	74,704 KB
実行使用メモリ	44,500 KB
最終ジャッジ日時	2024-06-11 05:14:36
合計ジャッジ時間	4,554 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	4 ms 5,376 KB
testcase_04	AC	1 ms 5,376 KB
testcase_05	AC	3 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	1 ms 5,376 KB
testcase_12	AC	3 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	32 ms 5,376 KB
testcase_16	AC	94 ms 7,632 KB
testcase_17	AC	231 ms 24,020 KB
testcase_18	AC	276 ms 23,904 KB
testcase_19	AC	239 ms 23,892 KB
testcase_20	AC	327 ms 23,896 KB
testcase_21	AC	139 ms 13,652 KB
testcase_22	AC	332 ms 23,896 KB
testcase_23	AC	118 ms 9,680 KB
testcase_24	AC	327 ms 23,900 KB
testcase_25	AC	437 ms 27,888 KB
testcase_26	AC	512 ms 44,500 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp:156:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  156 | main()
      | ^~~~

ソースコード

raw source code

#ifndef Modint_runtime_hpp
#define Modint_runtime_hpp
#include <cassert>
#include <iostream>

class modint_runtime
{
    long long val;
    int mod;
    friend constexpr bool mod_same(const modint_runtime &x, const modint_runtime &y) { return x.mod == y.mod; }
public:
    constexpr modint_runtime(long long x) : val(x), mod{} {}
    constexpr modint_runtime(long long x, int _mod) noexcept : val((x %= _mod) < 0 ? x + _mod : x), mod(_mod) {}
    constexpr bool mod_set() const noexcept { return mod; }
    constexpr long long value() const noexcept { return val; }
    constexpr int modulo() const noexcept { return mod; }
    constexpr modint_runtime operator++(int) noexcept { modint_runtime t = *this; return ++val, t; }
    constexpr modint_runtime &operator++() noexcept { return ++val, *this; }
    constexpr modint_runtime operator--(int) noexcept { modint_runtime t = *this; return --val, t; }
    constexpr modint_runtime &operator--() noexcept { return --val, *this; }
    constexpr modint_runtime &operator=(long long other) noexcept { return val = (other %= mod) < 0 ? other + mod : other, *this; }
    constexpr modint_runtime &operator+=(long long other) noexcept { return (val += other % mod) < mod ? 0 : val -= mod, *this; }
    constexpr modint_runtime &operator+=(const modint_runtime &other) noexcept { assert(mod_same(*this, other)); return (val += other.val) < mod ? 0 : val -= mod, *this; }
    constexpr modint_runtime &operator-=(long long other) noexcept { return (val += mod - other % mod) < mod ? 0 : val -= mod, *this; }
    constexpr modint_runtime &operator-=(const modint_runtime &other) noexcept { assert(mod_same(*this, other)); return (val += mod - other.val) < mod ? 0 : val -= mod, *this; }
    constexpr modint_runtime &operator*=(long long other) noexcept { return (val *= other % mod) %= mod, *this; }
    constexpr modint_runtime &operator*=(const modint_runtime &other) noexcept { assert(mod_same(*this, other)); return (val *= other.val) %= mod, *this; }
    constexpr modint_runtime &operator/=(long long other) noexcept { return *this *= inverse(modint_runtime{other, mod}); }
    constexpr modint_runtime &operator/=(const modint_runtime &other) noexcept { assert(mod_same(*this, other)); return *this *= inverse(other); }
    constexpr modint_runtime operator-() const noexcept { return modint_runtime(-val); }
    template <typename T> constexpr modint_runtime operator+(const T &other) const noexcept { return modint_runtime(*this) += other; }
    template <typename T> constexpr modint_runtime operator-(const T &other) const noexcept { return modint_runtime(*this) -= other; }
    template <typename T> constexpr modint_runtime operator*(const T &other) const noexcept { return modint_runtime(*this) *= other; }
    template <typename T> constexpr modint_runtime operator/(const T &other) const noexcept { return modint_runtime(*this) /= other; }
    constexpr bool operator==(const modint_runtime &other) const noexcept { assert(mod_same(*this, other)); return val == other.val; }
    constexpr bool operator!=(const modint_runtime &other) const noexcept { assert(mod_same(*this, other)); return val != other.val; }
    constexpr bool operator!() const noexcept { return !val; }
    friend constexpr modint_runtime operator+(long long x, modint_runtime y) noexcept { return {x + y.val, y.mod}; }
    friend constexpr modint_runtime operator-(long long x, modint_runtime y) noexcept { return {x - y.val, y.mod}; }
    friend constexpr modint_runtime operator*(long long x, modint_runtime y) noexcept { return {x % y.mod * y.val, y.mod}; }
    friend constexpr modint_runtime operator/(long long x, modint_runtime y) noexcept { return {x % y.mod * inverse(y).val, y.mod}; }
    friend constexpr modint_runtime inverse(const modint_runtime &other) noexcept
    {
        assert(other.mod && other.val);
        long long a{other.mod}, b{other.val}, u{}, v{1}, t{};
        while(b) t = a / b, a ^= b ^= (a -= t * b) ^= b, u ^= v ^= (u -= t * v) ^= v;
        return {u, other.mod};
    }
    friend constexpr modint_runtime pow(modint_runtime other, long long e) noexcept
    {
        if(e < 0) e = e % (other.mod - 1) + other.mod - 1;
        modint_runtime res{1, other.mod};
        while(e) { if(e & 1) res *= other; other *= other, e >>= 1; }
        return res;
    }
    friend std::ostream &operator<<(std::ostream &os, const modint_runtime &other) noexcept { return os << other.val; }
    friend std::istream &operator>>(std::istream &is, modint_runtime &other) noexcept { long long val; other = modint_runtime{(is >> val, val), other.mod}; return is; }
}; // class modint_runtime

#endif

#ifndef Factorial_runtime_hpp
#define Factorial_runtime_hpp
#include <vector>

class factorial_runtime
{
    const int mod;
    int n;
    std::vector<int> fact;
public:
    factorial_runtime(int _mod) : mod{_mod}, n{1}, fact{1} {}
    int modulo() const { return mod; }
    void reserve(int m)
    {
        if(m < n) return;
        m = 1 << (32 - __builtin_clz(m));
        fact.resize(m);
        for(int i = n; i < m; ++i) fact[i] = (long long)fact[i - 1] * i % mod;
        n = m;
    }
    modint_runtime operator()(const int x) noexcept { reserve(x); return {x < 0 ? 0 : fact[x], mod}; }
};

#endif

#ifndef Inverse_runtime_hpp
#define Inverse_runtime_hpp
#include <vector>

class inverse_runtime
{
    const int mod;
    int n;
    std::vector<int> inv;
public:
    inverse_runtime(int _mod) : mod{_mod}, n{2}, inv{0, 1} {}
    int modulo() const { return mod; }
    void reserve(int m)
    {
        if(m < n) return;
        m = 1 << (32 - __builtin_clz(m));
        inv.resize(m);
        for(int i = n; i < m; ++i) inv[i] = mod - (long long)mod / i * inv[mod % i] % mod;
        n = m;
    }
    modint_runtime operator()(const int x) noexcept { assert(x), reserve(x); return {inv[x], mod}; }
};

#endif // Inverse_runtime_hpp

#ifndef Inverse_factorial_runtime_hpp
#define Inverse_factorial_runtime_hpp
#include <cassert>
#include <vector>

class inverse_factorial_runtime
{
    inverse_runtime &inv_gen;
    const int mod;
    int n;
    std::vector<int> inv_fact;
public:
    inverse_factorial_runtime(inverse_runtime &_inv_gen) : inv_gen{_inv_gen}, mod{_inv_gen.modulo()}, n{1}, inv_fact{1} {}
    void reserve(int m)
    {
        if(m < n) return;
        m = 1 << (32 - __builtin_clz(m));
        inv_fact.resize(m);
        for(int i = n; i < m; ++i) inv_fact[i] = inv_fact[i - 1] * inv_gen(i).value() % mod;
        n = m;
    }
    modint_runtime operator()(const int x) noexcept { reserve(x); return {x < 0 ? 0 : inv_fact[x], mod}; }
};

#endif // Inverse_factorial_runtime_hpp

#ifndef Binomial_runtime_hpp
#define Binomial_runtime_hpp
#include <cassert>
#include <vector>

class binomial_runtime
{
    factorial_runtime &fact_gen;
    inverse_factorial_runtime &inv_fact_gen;
public:
    binomial_runtime(factorial_runtime &_fact_gen, inverse_factorial_runtime &_inv_fact_gen) : fact_gen(_fact_gen), inv_fact_gen(_inv_fact_gen) {}
    modint_runtime operator()(const int x, const int y) noexcept { return fact_gen(x) * inv_fact_gen(y) * inv_fact_gen(x - y); }
};

#endif

using namespace std;

main()
{
    const int mod=1e9+7;
    using mint=modint_runtime;

    factorial_runtime fac(mod);
    inverse_runtime inv(mod);
    inverse_factorial_runtime ifac(inv);
    binomial_runtime binom(fac,ifac);

    // binom.reserve(2200000);
    int x,y,z; cin>>x>>y>>z;
    mint ans{0,mod},s{1,mod};
    for(int k=x+y+z,f=1; k>=0; --k,f^=1)
    {
        mint tmp=s;
        if(x)
        {
            tmp*=binom(x+k-1,k-1);
        }
        if(y)
        {
            tmp*=binom(y+k-1,k-1);
        }
        if(z)
        {
            tmp*=binom(z+k-1,k-1);
        }
        ans+=tmp;
        s*=2;
        if(f)
        {
            s-=binom(x+y+z+1,k);
        }
        else
        {
            s+=binom(x+y+z+1,k);
        }
    }
    cout << ans << "\n";

    return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード