結果

問題 No.895 MESE
ユーザー edamame882edamame882
提出日時 2019-09-27 23:12:08
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,025 bytes
コンパイル時間 1,661 ms
コンパイル使用メモリ 173,620 KB
実行使用メモリ 8,980 KB
最終ジャッジ日時 2023-10-25 06:11:33
合計ジャッジ時間 5,463 ms
ジャッジサーバーID
(参考情報)
judge11 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,372 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 17 ms
4,348 KB
testcase_09 AC 14 ms
4,348 KB
testcase_10 AC 23 ms
4,348 KB
testcase_11 AC 31 ms
4,348 KB
testcase_12 AC 13 ms
4,348 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 #

#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;
  }
}

long long kaizyou(long long x){
  long long res = 1;
  for(int i = 1; i <= x; i++){
    res = (res * i) % MOD;
  }
  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);

  v[bit-1] += add;
  // ngを置く
  if(a > 0) dfs(bit-1,a-1,b);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  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