結果

問題 No.895 MESE
コンテスト
ユーザー edamame882
提出日時 2019-09-27 23:35:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 147 ms / 2,000 ms
コード長 3,370 bytes
コンパイル時間 1,927 ms
コンパイル使用メモリ 175,640 KB
実行使用メモリ 18,908 KB
最終ジャッジ日時 2024-09-25 02:27:31
合計ジャッジ時間 4,601 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

#define MOD (long)(1e9 + 7)

long long modPow(long long x, long long n){
  if(n == 0) return 1;
  if(n % 2 == 0) {
    long long sqrtX = modPow(x,n/2);
    return sqrtX * sqrtX % MOD ;
  }else{
    return x * modPow(x,n-1) % MOD;
  }
}
VI kai;
long long kaizyou(long long x){
  if(x == 1) return 1;
  if(x == 0) return 1;
  if(x > 1e6-1) assert(false && "error over flow");
  //cout << x << endl;
  if(kai[x] != -1) return kai[x];
  ll res = (x * kaizyou(x-1))%MOD;
  kai[x] = res;
  return res;
}

long long modCombi(long long a, long long b){
  if(b > a/2) return modCombi(a,a-b);
  return ((kaizyou(a) * modPow(kaizyou(b),MOD - 2)) % MOD)* modPow(kaizyou(a-b),MOD - 2) % MOD;
}

// Mod int
const int mod = 1000000007;
struct mint {
  ll x;
  mint():x(0){}
  mint(ll x):x((x%mod+mod)%mod){}
  // mint(ll x):x(x){}
  mint& fix() { x = (x%mod+mod)%mod; return *this;}
  mint operator-() const { return mint(0) - *this;}
  mint& operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;}
  mint& operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;}
  mint& operator*=(const mint& a){ (x*=a.x)%=mod; return *this;}
  mint operator+(const mint& a)const{ return mint(*this) += a;}
  mint operator-(const mint& a)const{ return mint(*this) -= a;}
  mint operator*(const mint& a)const{ return mint(*this) *= a;}
  bool operator<(const mint& a)const{ return x < a.x;}
  bool operator==(const mint& a)const{ return x == a.x;}
};
istream& operator>>(istream&i,mint&a){i>>a.x;return i;}
ostream& operator<<(ostream&o,const mint&a){o<<a.x;return o;}
typedef vector<mint> vm;
typedef vector<vm> vvm;
//
vector<mint> v;
void dfs(ll bit, ll a, ll b){
  // okを置く
  // mint add = modCombi(bit,a+b-1);
  // add *= kaizyou(a+b-1);
  // add *= (mint)modPow(kaizyou(b-1),MOD - 2);
  // add *= (mint)modPow(kaizyou(a),MOD - 2);
  // //cout << "add = " << add << ",";
  // add *= (mint)modPow(bit,MOD - 2);
  // add *= (mint)(bit - a - b + 1);
  mint add = kaizyou(bit-1);
  add *= (mint)modPow(kaizyou(b-1),MOD - 2);
  add *= (mint)modPow(kaizyou(a),MOD - 2);
  add *= (mint)modPow(kaizyou(bit-(a+b-1)-1),MOD - 2);
  v[bit-1] += add;
  // ngを置く
  if(a > 0) dfs(bit-1,a-1,b);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  kai.resize(1e6,-1);
  ll a,b,c;

  cin >> a >> b >> c;
  v.resize(a+b+c,0);
  dfs(a+b+c-2, a-1, b);
  mint ans = 0;
  for(int i = v.size()-2; i >= 0; i--) v[i] += v[i+1];
  rep(i,v.size()){
    mint tmp = modPow(2,i);
    tmp *= v[i];
    ans += tmp;
  }
  cout << ans << endl;
  return 0;
}
0