結果

問題 No.895 MESE
ユーザー bin101bin101
提出日時 2020-02-25 02:45:06
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 6,671 bytes
コンパイル時間 1,266 ms
コンパイル使用メモリ 111,652 KB
実行使用メモリ 17,400 KB
最終ジャッジ日時 2024-10-12 23:23:17
合計ジャッジ時間 5,301 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
13,640 KB
testcase_01 AC 6 ms
5,504 KB
testcase_02 AC 7 ms
5,632 KB
testcase_03 AC 6 ms
5,632 KB
testcase_04 AC 6 ms
5,632 KB
testcase_05 AC 6 ms
5,504 KB
testcase_06 AC 6 ms
5,632 KB
testcase_07 AC 5 ms
5,504 KB
testcase_08 AC 18 ms
5,632 KB
testcase_09 AC 15 ms
5,760 KB
testcase_10 AC 32 ms
5,888 KB
testcase_11 AC 34 ms
5,888 KB
testcase_12 AC 13 ms
5,632 KB
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include <map>
#include <set>
#include <tuple>
#include <iomanip>
#include <functional>
#include <complex>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;

template<class T,class U>constexpr bool chmin(T&a,const U b){if(a<=b)return false;a=b;return true;}
template<class T,class U>constexpr bool chmax(T&a,const U b){if(a>=b)return false;a=b;return true;}
#define bit(n,k) ( (n>>k)&1 )

//デバッグ
template<class T>
void Vout(vector<T> &V){
    cout<<"\nstart\n";
    const int sz=V.size();
    for(int i=0;i<sz;i++){
        cout<<i<<" "<<V[i]<<'\n';
    }
    cout<<"end\n"<<endl;
}

template<class T>
void VPout(vector<T> &V){
    cout<<"\nstart\n";
    const int sz=V.size();
    for(int i=0;i<sz;i++){
        cout<<i<<" "<<V[i].first<<" "<<V[i].second<<'\n';
    }
    cout<<"end\n"<<endl;
}


//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


constexpr int MAX=1<<30;
constexpr ll INF=1LL<<62;
constexpr int MOD=1e9+7;
int dx[]={1,-1,0,0},dy[]={0,0,-1,1};

//__builtin_popcount(S);
//#define int ll
//vector<vector<int>> data(3, vector<int>(4));
//vector.resize(a,vector<int>(b,-1));
//vector<vector<vector<要素の型>>> 変数名(要素数1, vector<vector<要素の型>>(要素数2, vector<要素の型>(要素数3, 初期値)));

struct ModInt{
    using u64=uint_fast64_t;
    u64 a;
    constexpr ModInt() :a(0){}
    constexpr ModInt(ll x) :a((x>=0)?(x%MOD):(x%MOD+MOD) ) {}

    inline constexpr ModInt operator+(const ModInt rhs)const noexcept{
        return ModInt(*this)+=rhs;
    }
    inline constexpr ModInt operator-(const ModInt rhs)const noexcept{
        return ModInt(*this)-=rhs;
    }
    inline constexpr ModInt operator*(const ModInt rhs)const noexcept{
        return ModInt(*this)*=rhs;
    }
    inline constexpr ModInt operator/(const ModInt rhs)const noexcept{
        return ModInt(*this)/=rhs;
    }
    inline constexpr ModInt operator+(const ll rhs) const noexcept{
        return ModInt(*this)+=rhs;
    }
    inline constexpr ModInt operator-(const ll rhs)const noexcept{
        return ModInt(*this)-=rhs;
    }
    inline constexpr ModInt operator*(const ll rhs)const noexcept{
        return ModInt(*this)*=rhs;
    }
    inline constexpr ModInt operator/(const ll rhs)const noexcept{
        return ModInt(*this)/=rhs;
    }

    inline constexpr ModInt &operator+=(const ModInt rhs)noexcept{
        a+=rhs.a;
        if(a>=MOD) a-=MOD;
        return *this;
    }
    inline constexpr ModInt &operator-=(const ModInt rhs)noexcept{
        if(rhs.a>a) a+=MOD;
        a-=rhs.a;
        return *this;
    }
    inline constexpr ModInt &operator*=(const ModInt rhs)noexcept{
        a=(a*rhs.a)%MOD;
        return *this;
    }
    inline constexpr ModInt &operator/=(ModInt rhs)noexcept{
        a=(a*rhs.inverse().a)%MOD;
        return *this;
    }
    inline constexpr ModInt &operator+=(const ll rhs)noexcept{
        a+=rhs;
        if(a>=MOD) a-=MOD;
        return *this;
    }
    inline constexpr ModInt &operator-=(const ll rhs)noexcept{
        if(rhs>a) a+=MOD;
        a-=rhs;
        return *this;
    }
    inline constexpr ModInt &operator*=(const ll rhs)noexcept{
        a=(a*rhs)%MOD;
        return *this;
    }
    inline constexpr ModInt &operator/=(ll rhs)noexcept{
        a=(a*ModInt(rhs).inverse().a)%MOD;
        return *this;
    }

    inline constexpr ModInt operator=(ll x)noexcept{
        x%=MOD;
        if(x<0) x+=MOD;
        a=x;
        return *this;
    }

    inline constexpr bool operator==(const ModInt p)const noexcept{
        return a==p.a;
    }

    inline constexpr bool operator!=(const ModInt p)const noexcept{
        return a!=p.a;
    }

    inline constexpr ModInt pow(ll N) const noexcept{
        ModInt ans(1LL),p(a);
        while(N>0){
            if(bit(N,0)){
                ans*=p;
            }
            p*=p;
            N>>=1;
        }
        return ans;
    }
    inline constexpr ModInt inverse() const noexcept{
        return pow(MOD-2);
    }

};
inline constexpr ModInt operator+(const ll &a,const ModInt &b)noexcept{
    return ModInt(a)+=b;
}
inline constexpr ModInt operator-(const ll &a,const ModInt &b)noexcept{
    return ModInt(a)-=b;
}
inline constexpr ModInt operator*(const ll &a,const ModInt &b)noexcept{
    return ModInt(a)*=b;
}
inline constexpr ModInt operator/(const ll &a,const ModInt &b)noexcept{
    return ModInt(a)/=b;
}


inline constexpr ModInt Mr(ll p){
    p%=MOD;
    if(p<0) p+=MOD;
    return ModInt(p);
}

struct Binominal{
    vector<ModInt> fac,finv,inv; //fac[n]:n! finv:(n!)の逆元
    int sz;
    Binominal(int n=0) :sz(0){
        init(n);
    }
    inline void init(int n){
        fac.resize(n+1,1);
        finv.resize(n+1,1);
        inv.resize(n+1,1);
        for(int i=2;i<=n;i++){
            fac[i]=fac[i-1]*i;
            inv[i]=MOD-inv[MOD%i]*(MOD/i);
            finv[i]=finv[i-1]*inv[i];
        }
    }
    //nCk(n,k<=N) をO(1)で求める
    inline ModInt com(int n,int k){
        if(n<k) return ModInt(0);
        if(n<0 || k<0) return ModInt(0);
        if(n>sz) init(n);
        return fac[n]*finv[k]*finv[n-k];
    }
    //nCk(k<=N) をO(k)　で求める 
    inline ModInt rcom(ll n,int k){
        if(n<0 || k<0 || n<k) return ModInt(0);
        if(k>sz) init(k);
        ModInt ret(1);
        for(int i=0;i<k;i++){
            ret*=(n-i);
        }
        ret*=finv[k];
        return ret;
    }

    //重複組み合わせ n種類のものから重複を許してk個を選ぶ
    //〇がn個,|がk個
    inline ModInt h(int n,int k){
        return com(n+k-1,k);
    }
};
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    cout<<fixed<<setprecision(10);
 
    int a,b,c;
    cin>>a>>b>>c;
    int sum=a+b+c;
    ModInt ans(0),co(0);
    vector<ModInt> t(310000);
    t[0]=1;
    for(int i=1;i<310000;i++){
        t[i]=t[i-1]*2;
    }
    for(int i=1;i<310000;i++){
        t[i]+=t[i-1];
    }
    Binominal B;
    for(int i=1;i<=a;i++){
        int sum=a-i+b-1+c;
        co=B.com(sum,c)*B.com(sum-c,b-1);
        ans+=co*c/sum*t[sum-1];
    }
    cout<<ans.a<<endl;
}
0