CODE FESTIVAL 2016 Grand Final(Parallel)

Submission #1017524

Source codeソースコード

#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}



template<lint mod>
struct Int_{
  unsigned x;
  unsigned mpow(Int_ a,unsigned k){
    Int_ res=1;
    while(k){
      if(k&1) res=res*a;
      a=a*a;
      k>>=1;
    }
    return res.x;
  }
  unsigned inverse(Int_ a){
    return mpow(a,mod-2);
  }
  Int_(): x(0) { }
  Int_(long long sig) {
    int sigt=sig%mod;
    if(sigt<0) sigt+=mod;
    x=sigt;
  }
  unsigned get() const { return (unsigned)x; }
  
  Int_ &operator+=(Int_ that) { if((x += that.x) >= mod) x -= mod; return *this; }
  Int_ &operator-=(Int_ that) { if((x += mod - that.x) >= mod) x -= mod; return *this; }
  Int_ &operator*=(Int_ that) { x = (unsigned long long)x * that.x % mod; return *this; }
  Int_ &operator=(Int_ that) { x=that.x; return *this;}
  Int_ &operator/=(Int_ that) { x=(unsigned long long) x * inverse(that.x)%mod; return *this;}
  bool operator==(Int_ that) const { return x==that.x; }
  bool operator!=(Int_ that) const { return x!=that.x; }

  Int_ operator-() const { return Int_(0)-Int_(*this);}
  Int_ operator+(Int_ that) const { return Int_(*this) += that; }
  Int_ operator-(Int_ that) const { return Int_(*this) -= that; }
  Int_ operator*(Int_ that) const { return Int_(*this) *= that; }
  Int_ operator/(Int_ that) const { return Int_(*this) /= that; }

};

namespace std{
  template<lint mod>
  ostream &operator <<(ostream& out,const Int_<mod>& a){
    out<<a.get();
    return out;
  }
  template<lint mod>
  istream &operator >>(istream& in,Int_<mod>& a){
    in>>a.x;
    return in;
  }
};

typedef Int_<1000000007> Int;
//const int INF=5e8;
int n,a,b,c;
Int Co[5005][5005];
Int fact[5005],invf[5005];
int main(){
  cin>>n>>a>>b>>c;

  fact[0]=invf[0]=1;
  Int one=1;
  REP(i,5002){
    fact[i+1]=fact[i]*(i+1);
    invf[i+1]=one/fact[i+1];
    Co[i][0]=1;
    REP(j,i) Co[i][j+1]=Co[i-1][j+1]+Co[i-1][j];
  }

  if(b&1){
    puts("0");
    return 0;
  }
  Int res=0;
  REP(i,min(a,c)+1) REP(j,c+1){
    if((c-i-j)%3 || (c-i-j)<0) continue;
    if(b==0 && j>0) continue;

    int A=a-i;
    int B=i;
    int C=(c-i-j)/3;
    int D=b/2;

    Int tmp=fact[A+B+C+D]*invf[A]*invf[B]*invf[C]*invf[D];
    if(b>0) tmp*=Co[j+D-1][j];
    res+=tmp;
  }
  cout<<res<<endl;
  return 0;
}



Submission

Task問題 J - 123 Pairs
User nameユーザ名 hogloid
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1500
Source lengthソースコード長 3240 Byte
File nameファイル名
Exec time実行時間 136 ms
Memory usageメモリ使用量 98176 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - example0.txt,example1.txt
All 1500 / 1500 000.txt,001.txt,002.txt,003.txt,004.txt,005.txt,006.txt,007.txt,008.txt,009.txt,010.txt,011.txt,012.txt,013.txt,014.txt,015.txt,016.txt,017.txt,018.txt,019.txt,020.txt,021.txt,022.txt,023.txt,024.txt,025.txt,026.txt,027.txt,028.txt,029.txt,030.txt,031.txt,032.txt,033.txt,034.txt,035.txt,036.txt,037.txt,038.txt,039.txt,040.txt,041.txt,042.txt,043.txt,044.txt,045.txt,046.txt,047.txt,048.txt,049.txt,example0.txt,example1.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
000.txt AC 130 ms 98176 KB
001.txt AC 116 ms 98176 KB
002.txt AC 116 ms 98176 KB
003.txt AC 115 ms 98176 KB
004.txt AC 117 ms 98176 KB
005.txt AC 115 ms 98176 KB
006.txt AC 115 ms 98176 KB
007.txt AC 115 ms 98176 KB
008.txt AC 115 ms 98176 KB
009.txt AC 116 ms 98176 KB
010.txt AC 115 ms 98176 KB
011.txt AC 115 ms 98176 KB
012.txt AC 115 ms 98176 KB
013.txt AC 115 ms 98176 KB
014.txt AC 116 ms 98176 KB
015.txt AC 132 ms 98176 KB
016.txt AC 117 ms 98176 KB
017.txt AC 122 ms 98176 KB
018.txt AC 118 ms 98176 KB
019.txt AC 121 ms 98176 KB
020.txt AC 117 ms 98176 KB
021.txt AC 129 ms 98176 KB
022.txt AC 118 ms 98176 KB
023.txt AC 120 ms 98176 KB
024.txt AC 130 ms 98176 KB
025.txt AC 120 ms 98176 KB
026.txt AC 128 ms 98176 KB
027.txt AC 133 ms 98176 KB
028.txt AC 123 ms 98176 KB
029.txt AC 124 ms 98176 KB
030.txt AC 129 ms 98176 KB
031.txt AC 130 ms 98176 KB
032.txt AC 117 ms 98176 KB
033.txt AC 116 ms 98176 KB
034.txt AC 120 ms 98176 KB
035.txt AC 125 ms 98176 KB
036.txt AC 117 ms 98176 KB
037.txt AC 115 ms 98176 KB
038.txt AC 136 ms 98176 KB
039.txt AC 115 ms 98176 KB
040.txt AC 116 ms 98176 KB
041.txt AC 119 ms 98176 KB
042.txt AC 116 ms 98176 KB
043.txt AC 115 ms 98176 KB
044.txt AC 115 ms 98176 KB
045.txt AC 116 ms 98176 KB
046.txt AC 115 ms 98176 KB
047.txt AC 115 ms 98176 KB
048.txt AC 116 ms 98176 KB
049.txt AC 116 ms 98176 KB
example0.txt AC 115 ms 98176 KB
example1.txt AC 115 ms 98176 KB